Multi-stage Marathon

Bobo is organizing a marathon contest. The contest has $n$ checkpoints, labeled $1, 2, ..., n$. You are given a binary matrix $G$. $G_{u,v} = 1$ means 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$. The road system is complicated, so players move randomly. If a player is at checkpoint $u$ at moment $t$, then at moment $t + 1$ the player appears at each checkpoint $v$ with $G_{u,v} = 1$ with equal probability.

Let $E_t = P Q^{-1} \bmod (10^9+7)$, where $P/Q$ is the expected number of players at checkpoint $n$ at moment $t$, and $Q Q^{-1} \equiv 1 \pmod{10^9+7}$. Bobo wants to know $E_1 \oplus E_2 \oplus \dots \oplus E_T$, where $\oplus$ is bitwise exclusive or.

The first line contains three integers $n$, $m$, and $T$ ($1 \le n \le 70$, $1 \le m \le 10^4$, $1 \le T \le 2 \times 10^6$). Each of the next $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$. Each of the last $m$ lines contains two integers $t_i$ and $v_i$ ($1 \le t_1 < t_2 < \dots < t_m \le T$, $1 \le v_i \le n$).

Print one integer, the result.