1078 : Parity of Tuples (Easy)

Description

Bobo has n m-tuple v₁, v₂, …, v_n, where v_i = (a_i, 1, a_i, 2, …, a_i, m). He wants to find count(x) which is the number of v_i where a_i, j ∧ x has odd number of ones in its binary notation for all j. Note that ∧ denotes the bitwise-and.

Find $\sum_{x = 0}^{2^k - 1} \mathrm{count}(x) \cdot 3^x$ modulo (10⁹ + 7) for given k.

Input

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, …, a_i, m.

• 1 ≤ n ≤ 10⁴
• 1 ≤ m ≤ 10
• 1 ≤ k ≤ 30
• 0 ≤ a_i, j < 2^k.
• There are at most 100 test cases, and at most 1 of them have n > 10³ or m > 5.

Output

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

Sample Input

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

Sample Output

12
3
1122012

Hint

Source

Author

ftiasch