Bobo 正在组织一场马拉松比赛。比赛包含 $n$ 个检查点，编号为 $1, 2, \dots, n$。给定一个二进制矩阵 $G$。在该矩阵中，$G_{u,v} = 1$ 表示存在一条从检查点 $u$ 到检查点 $v$ 的有向道路，$G_{u,v} = 0$ 表示不存在这样的道路。

共有 $m$ 名选手。第 $i$ 位选手在时刻 $t_i$ 从检查点 $v_i$ 出发。由于道路系统复杂，选手的行为非常随机。具体来说，如果一名选手在时刻 $t$ 位于检查点 $u$，那么在时刻 $(t+1)$，该选手将以相等的概率出现在任何满足 $G_{u,v} = 1$ 的检查点 $v$。

令 $E_t = P \cdot Q^{-1} \pmod{10^9 + 7}$，其中 $\frac{P}{Q}$ 是时刻 $t$ 位于检查点 $n$ 的选手人数的期望值，且 $Q \cdot Q^{-1} \equiv 1 \pmod{10^9 + 7}$。Bobo 想知道 $E_1 \oplus E_2 \oplus \dots \oplus E_T$ 的值。注意 “$\oplus$” 表示按位异或运算。

输入格式

第一行包含三个整数 $n, m$ 和 $T$ ($1 \le n \le 70, 1 \le m \le 10^4, 1 \le T \le 2 \cdot 10^6$)。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $n$ 的二进制字符串 $G_{i,1}, G_{i,2}, \dots, G_{i,n}$。保证 $G_{i,i} = 1$ 始终成立。

最后 $m$ 行中，第 $i$ 行包含两个整数 $t_i$ 和 $v_i$ ($1 \le t_1 < t_2 < \dots < t_m \le T, 1 \le v_i \le n$)。

输出格式

输出一个整数，表示结果。

样例

样例输入 1

2 2 2
11
11
1 1
2 2

样例输出 1

500000005

样例输入 2

3 1 6
110
011
101
1 1

样例输出 2

191901811