Background

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

Problem Description

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$.

Input Format

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 Format

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.

2 3 5
7 18 4
10 6 3

375000011

6 5 0
9 4 6 2 3
6 4 4 0 1
2 0 4 3 0
1 5 7 3 4
5 0 2 1 5
6 4 9 8 3

99609378

Hint

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:

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