시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 1 1 1 100.000%

문제

Bobo is organizing a marathon contest. The contest contains $n$ checkpoints which are conveniently labeled with $1, 2, \dots, n$. You are given a binary matrix $G$. In this matrix, $G_{u, v} = 1$ indicates that there is a directed road from checkpoint $u$ to checkpoint $v$, and $G_{u, v} = 0$ means there is no such road.

There are $m$ players. The $i$-th player starts at checkpoint $v_i$ at moment $t_i$. As the road system is complicated, players behave quite randomly. More precisely, if at moment $t$ a player is at checkpoint $u$, at moment $(t + 1)$ this player will appear at any checkpoint $v$ such that $G_{u, v} = 1$ with equal probability.

Let $E_t = P \cdot Q^{-1} \bmod (10^9+7)$ where $\frac{P}{Q}$ is the expected number of players at checkpoint $n$ at moment $t$, and $Q \cdot Q^{-1} \equiv 1 \mod{(10^9+7)}$. Bobo would like to know $E_1 \oplus E_2 \oplus \dots \oplus E_T$. Note that "$\oplus$" denotes bitwise exclusive-or.

입력

The first line contains three integers $n$, $m$ and $T$ ($1 \leq n \leq 70$, $1 \leq m \leq 10^4$, $1 \leq T \leq 2 \cdot 10^6$).

The $i$-th of the following $n$ lines contains a binary string $G_{i, 1}, G_{i, 2}, \dots, G_{i, n}$ of length $n$. It is guaranteed that $G_{i, i} = 1$ is always true.

The $i$-th of the last $m$ lines contains two integers $t_i$ and $v_i$ ($1 \leq t_1 < t_2 < \dots < t_m \leq T$, $1 \leq v_i \leq n$).

출력

Output an integer which denotes the result.

예제 입력 1

2 2 2
11
11
1 1
2 2

예제 출력 1

500000005

예제 입력 2

3 1 6
110
011
101
1 1

예제 출력 2

191901811