Problem Description

Zhenxun is too lazy to clean up bombs himself, so Minori has invented an automatic floor-cleaning robot to clean the room.

Zhenxun's room consists of \( n \) rows and \( m \) columns of square tiles, with the dust amount on the tile at the \( i \)-th row and \( j \)-th column being \( a_{i,j} \). Minori's robot starts from the top-left corner of the room and moves one step to the right or down at random each time.

If the robot reaches the bottom-right corner without hitting the wall, it will return the bitwise XOR sum of the dust amounts of all tiles it passed to Minori. If the robot hits the wall before reaching the bottom-right corner, i.e., if the target position does not exist in some step, the robot will return an error value \( x \) and stop moving.

Given the dust amounts on each tile in Zhenxun's room for a certain day, please calculate the expected value of the robot's return value.

Formally, given a \( n \times m \) matrix \( a \), where the weight of the \( i \)-th row and \( j \)-th column is \( a_{i,j} \), a robot starts from \( (1,1) \). It moves to \( (i,j+1) \) or \( (i+1,j) \) with equal probability \( \frac{1}{2} \). If the robot reaches \( (n,m) \), it returns the bitwise XOR sum of the path weights. If it moves outside the matrix before reaching \( (n,m) \), it returns \( x \). Calculate the expected return value modulo \( 10^9+7 \).

Input Format

The first line contains three integers \( n \), \( m \), and \( x \), representing the number of rows, columns, and the error value, respectively.

The next \( n \) lines each contain \( m \) integers, where the \( i \)-th line and \( j \)-th column integer represents \( a_{i,j} \), describing the dust amount on each tile.

Output Format

A single line containing an integer \( ans \), representing the expected value modulo \( 10^9+7 \).

If you are unsure about modulo operations with rational numbers, please refer to P2613 【模板】有理数取余.

Sample Input and Output

Input Sample #1

2 3 5
7 18 4
10 6 3

Output Sample #1

375000011

Input Sample #2

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

Output Sample #2

99609378

Notes

Sample 1 Explanation

If the robot moves down first:

• If the robot moves down again, it hits the wall, returning \( 5 \), with a probability of \( \frac{1}{4} \);

• If the robot moves right, then:

• If the robot moves down again, it hits the wall, returning \( 5 \), with a probability of \( \frac{1}{8} \);

• If the robot moves right again, it reaches the bottom-right corner, returning \( 7 \oplus 10 \oplus 6 \oplus 3 = 8 \), with a probability of \( \frac{1}{8} \);

If the robot moves right first:

• If the robot moves down, then:

• If the robot moves down again, it hits the wall, returning \( 5 \), with a probability of \( \frac{1}{8} \);

• If the robot moves right again, it reaches the bottom-right corner, returning \( 7 \oplus 18 \oplus 6 \oplus 3 = 16 \), with a probability of \( \frac{1}{8} \);

• If the robot moves right, then:

• If the robot moves down, it reaches the bottom-right corner, returning \( 7 \oplus 18 \oplus 4 \oplus 3 = 18 \), with a probability of \( \frac{1}{8} \);

• If the robot moves right again, it hits the wall, returning \( 5 \), with a probability of \( \frac{1}{8} \);

Thus, the expected return value is \( \frac{3 \times 5 + 8 + 16 + 18}{8} + \frac{5}{4} = \frac{67}{8} \), which modulo \( 10^9+7 \) is \( 375000011 \).

Data Range

For all data, \( 1 \leq n, m \leq 10^3 \), \( 0 \leq a_{i,j}, x \leq 10^9 \).

This problem consists of 22 test cases and uses bundled testing. Subtasks and data point distribution are as follows:

Hints

\( \oplus \) denotes 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 \).

见题面 Input 部分

见题面 Output 部分