Dusty Room Robot

A fully automated cleaning robot is used to clean a room by traversing a grid of square tiles. The room has n rows and m columns. The dust amount on the tile in row i and column j is given by \(a_{i,j}\). Every day the robot starts at the upper‐left corner (cell \((1,1)\)) and, at each step, it randomly chooses to move either right or down with equal probability \(\frac{1}{2}\).

If the robot reaches the bottom‐right corner (cell \((n,m)\)) without ever moving outside the grid, it returns the bitwise XOR of the dust amounts on all the tiles it visited. Otherwise, if at any step the chosen move would take the robot out of the grid (i.e. the cell does not exist), the robot stops immediately and returns an error value \(x\). Given the matrix \(a\) and the error value \(x\), compute the expected value of the robot's returned value modulo \(10^9+7\).

Formally, let the matrix \(a\) be an \(n\times m\) grid with the dust amounts \(a_{i,j}\). A robot starts at \((1,1)\) with an initial accumulator of 0. Upon arriving at a cell, the robot updates the accumulator to be the XOR of its current value and the dust at that cell. Then, it randomly chooses to move right or down (each with probability \(\frac{1}{2}\)). If the chosen move is out-of-bound (i.e. does not lie within \(1\le i\le n,\ 1\le j\le m\)), the robot terminates immediately and returns \(x\). If the robot reaches \((n,m)\), it returns the final accumulator value, which is the XOR of dust from all visited cells. Your task is to calculate the expected returned value modulo \(10^9+7\).

Note: Since the XOR operation does not behave linearly with respect to expectation, a typical approach is to consider each bit independently and use dynamic programming along with probability (fractions) modulo \(10^9+7\). All calculations involving fractions should be handled modulo \(10^9+7\) using the modular inverse of 2.

The final answer is an integer representing the expected value modulo \(10^9+7\).

inputFormat

The first line contains three integers \(n\), \(m\) and \(x\) \((1\le n,m\le 1000,\ 0\le x < 2^{31})\) -- the number of rows, columns and the error value respectively.

Then follow \(n\) lines, each containing \(m\) integers. The \(j\)-th integer on the \(i\)-th line is \(a_{i,j}\) \((0\le a_{i,j} < 2^{31})\), representing the dust amount on the tile in row \(i\) and column \(j\).

outputFormat

Output a single integer, the expected returned value of the robot modulo \(10^9+7\).

sample

1 1 7
3

3