Bobo 有 $n$ 个 $m$ 元组 $v_1, v_2, \dots, v_n$，其中 $v_i = (a_{i, 1}, a_{i, 2}, \dots, a_{i, m})$。他想要计算 $\mathrm{count}(x)$，即满足对于所有 $j$， $a_{i, j} \wedge x$ 的二进制表示中 1 的个数为奇数的 $v_i$ 的数量。注意 $\wedge$ 表示按位与运算。

对于给定的 $k$，求 $\sum_{x = 0}^{2^k - 1} \mathrm{count}(x) \cdot 3^x$ 对 $(10^9+7)$ 取模的结果。

输入格式

输入包含多组测试数据，以文件结束符（EOF）终止。

每组测试数据的第一行包含三个整数 $n$、$m$ 和 $k$。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$。

• $1 \leq n \leq 10^4$
• $1 \leq m \leq 10$
• $1 \leq k \leq 30$
• $0 \leq a_{i, j} < 2^k$
• 最多有 $100$ 组测试数据，其中 $n > 10^3$ 或 $m > 5$ 的测试数据最多只有 $1$ 组。

输出格式

对于每组测试数据，输出一个整数，表示计算结果。

样例

样例输入 1

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

样例输出 1

12
3
1122012