CSG-CPC
Online Judge

1078 : Parity of Tuples (Easy)

         Time Limit: 5 Sec     Memory Limit: 512 Mb     Submitted: 2     Solved: 2    

Description

Bobo has n m-tuple v1, v2, …, vn, where vi = (ai, 1, ai, 2, …, ai, m). He wants to find count(x) which is the number of vi where ai, 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 (109 + 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 ai, 1, ai, 2, …, ai, m.

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

Output

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

Sample

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

Hint

Author

ftiasch