19364번 - Multi-stage Marathon 다국어

문제

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.

제한

힌트