Little Q 喜欢 $k$ 进制下的正大整数，但并非所有大整数他都喜欢。他不喜欢包含数字 $0$ 的整数（包括前导零）。此外，他对每个数字出现的次数有特殊要求。形式化地，他的偏好可以用一个二进制矩阵 $g_{1..k-1, 0..n}$ 来描述，其中对于每个从 $1$ 到 $k-1$ 的数字 $i$，如果 $g_{i,j} = 0$，则他不喜欢恰好包含 $j$ 个数字 $i$ 的整数。同时，他也不接受任何数字出现超过 $n$ 次的情况。整数必须至少包含一个数字。

Little Q 的喜好每天都在变化。总共有 $m$ 天，在第 $i$ 天，$g_{u_i, v_i}$ 的值会翻转（$0$ 变为 $1$，$1$ 变为 $0$）。令 $cnt(i)$ 表示在第 $i$ 天的变化后 Little Q 喜欢的大整数个数，$cnt(0)$ 表示所有变化之前的答案。你的任务是计算以下值：

$$\left( \sum_{i=0}^{m} cnt(i) \right) \pmod{786\,433}$$

输入格式

第一行包含三个整数 $k, n$ 和 $m$：进制数、上限以及天数（$3 \le k \le 10$，$1 \le n \le 1.4 \cdot 10^4$，$1 \le m \le 200$）。

接下来的 $k-1$ 行中，第 $i$ 行包含 $n+1$ 个整数 $g_{i,0}, g_{i,1}, \dots, g_{i,n}$（$0 \le g_{i,j} \le 1$）。它们共同提供了初始矩阵 $g$。

随后有 $m$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示在第 $i$ 天，$g_{u_i, v_i}$ 的值被翻转（$1 \le u_i \le k-1$，$0 \le v_i \le n$）。

输出格式

输出一行，包含一个整数：问题的答案。

样例

输入 1

3 2 2
1 0 1
0 1 0
1 1
1 2

输出 1

13