题目描述

Bobo has n m-tuple $v_1, v_2, \dots, v_n$​, where $v_i = (a_{i, 1}, a_{i, 2}, \dots, a_{i, m})$. He wants to find $\mathrm{count}(x)$ which is the number of $v_i$​ where $a_{i, j} \wedge x$ has odd number of ones in its binary notation for all j. Note that $\wedge$ denotes the bitwise-and.

Print $ \bigoplus_{x = 0}^{2^k - 1} \left(\mathrm{count}(x) \cdot 3^x \bmod (10^9+7)\right) $ for given k, where $\oplus$ denotes bitwise-xor.

输入格式

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains three integers n, m and k. The ith of the following n lines contains m integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$.

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 10$
• $1 \leq k \leq 20$
• $0 \leq a_{i, j} < 2^k$ .
• There is exactly one test case with $n = 10^5$, m = 10 and k = 20. The other 300 test cases have $n \leq 10^3$, $m \leq 4$ and $k \leq 10$.

输出格式

For each test case, print an integer which denotes the result.

样例

样例输入

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

样例输出

10
3
1102106