다단계 마라톤

Bobo는 마라톤 대회를 준비하고 있다. 대회에는 $1, 2, ..., n$으로 번호가 매겨진 검문소 $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 Q^{-1} \bmod (10^9+7)$로 정의한다. 여기서 $P/Q$는 시각 $t$에 검문소 $n$에 있는 참가자 수의 기댓값이고, $Q 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 \times 10^6$). 다음 $n$개 줄에는 길이 $n$인 이진 문자열 $G_{i,1} G_{i,2} \dots G_{i,n}$이 한 줄씩 주어진다. $G_{i,i} = 1$은 항상 성립한다. 마지막 $m$개 줄에는 정수 $t_i$와 $v_i$가 주어진다 ($1 \le t_1 < t_2 < \dots < t_m \le T$, $1 \le v_i \le n$).

결과를 나타내는 정수 하나를 출력한다.