P10267 Robot

 > Illustrator: 白森 さわ (from pixiv), please contact to remove if infringement.

Mafuyu is even too lazy to clean up bombs by herself, so Minami invented a fully automatic vacuum robot to clean the room. Mafuyu’s room consists of $n$ rows and $m$ columns of tiles. The amount of dust on the tile in row $i$, column $j$ is $a_{i,j}$. Every day, Minami’s robot starts from the upper-left corner of the room, and each time it randomly moves one step either right or down. If the robot reaches the lower-right corner without hitting a wall, it will return to Minami **the xor sum of the dust amounts on all tiles it passed through**. If the robot hits a wall before reaching the lower-right corner, meaning the target position of some step does not exist (moves outside the grid), then the robot returns an error value $x$ and stops moving. Given the dust amount on every tile in Mafuyu’s room on a certain day, compute the expected value of the robot’s return value. Formally, given an $n \times m$ matrix $a$, where the weight of cell $(i,j)$ is $a_{i,j}$, a robot starts from $(1,1)$. Each step, with probability $\frac{1}{2}$ it moves from $(i,j)$ to $(i,j+1)$, and with probability $\frac{1}{2}$ it moves to $(i+1,j)$. If it moves to $(n,m)$, it returns the **xor sum of the weights on the path**. If at any time before reaching $(n,m)$ it moves outside the matrix, it returns $x$. Find the expected value of the return value. Output the answer modulo $10^9+7$.

The first line contains three integers $n,m,x$, representing the number of rows, the number of columns, and the error value. The next $n$ lines each contain $m$ integers. The integer in row $i$, column $j$ is $a_{i,j}$, describing the dust amount on each tile.

Output one integer $ans$, the expected value modulo $10^9+7$. If you are confused about taking a rational number modulo, please refer to [P2613 【Template】Modulo of Rational Numbers](https://www.luogu.com.cn/problem/P2613).

**Sample** $\mathbf{1}$ **Explanation** If the robot moves down on the first step, then: - If the robot moves down on the second step, it hits a wall and returns $5$, with probability $\frac{1}{4}$. - If the robot moves right on the second step, then: - If the robot moves down on the third step, it hits a wall and returns $5$, with probability $\frac{1}{8}$. - If the robot moves right on the third step, it reaches the lower-right corner and returns $7\oplus 10\oplus 6\oplus 3=8$, with probability $\frac{1}{8}$. If the robot moves right on the first step, then: - If the robot moves down on the second step, then: - If the robot moves down on the third step, it hits a wall and returns $5$, with probability $\frac{1}{8}$. - If the robot moves right on the third step, it reaches the lower-right corner and returns $7\oplus 18\oplus 6\oplus 3=16$, with probability $\frac{1}{8}$. - If the robot moves right on the second step, then: - If the robot moves down on the third step, it reaches the lower-right corner and returns $7\oplus 18\oplus 4\oplus 3=18$, with probability $\frac{1}{8}$. - If the robot moves right on the third step, it hits a wall and returns $5$, with probability $\frac{1}{8}$. Therefore, the expected return value is $\frac{3\times 5+8+16+18}{8}+\frac{5}{4}=\frac{67}{8}$, which is $375000011$ modulo $10^9+7$. **Constraints** For all data, $1\leq n,m\leq 10^3$, $0\leq a_{i,j},x\leq 10^9$. There are $22$ test points in total. This problem **uses bundled judging**. The subtasks and test point distribution are as follows: | Subtask ID | Test Point ID | Special Property | Score | | :-: | :-: | :-: | :-: | | $0$ | $1\sim 4$ | $n,m\leq 12$ | $10$ | | $1$ | $5\sim 8$ | $n,m\leq 20$ | $20$ | | $2$ | $9\sim 12$ | $a_{i,j}\leq 20$ | $20$ | | $3$ | $13\sim 16$ | $x=0$ | $20$ | | $4$ | $17\sim 22$ | No special restrictions | $30$ | **Hint** $\oplus$ denotes xor (bitwise xor). The xor sum of $x_1,x_2,x_3,\cdots,x_n$ is $x_1\oplus x_2\oplus x_3\oplus\cdots \oplus x_n$. Translated by ChatGPT 5