Warning: 附加文件中的 trans.cpp 不可用，因此本题暂时无法解决。
小 Bo 特别喜欢数列。有一天他偶尔得到了一个序列，这个序列是无限长的，但特殊的是这个序列中只有 $N$ 个位置有值。 小 Bo 将这个序列存在了自己的笔记本中。不幸的是，有一天他忘记锁屏了。一个熊孩子看到了他的数列，决定做一些恶作剧。
熊孩子先将这个序列 $A$ 复制到一个新的序列 $B$ 里，然后做了 $t$ 次操作，每次将 $B$ 赋值为 $A$ 与 $B$ 的 狄里克雷卷积 结果。 最后，熊孩子又新建了一个序列 $C$，并将 $B$ 中的第 $i$ 项加到了 $C$ 中的第 $trans(i, M)$ 项，并输出了序列 $C$。
这时，小 Bo 突然回来了，熊孩子落荒而逃，匆忙之中落下了记录着 $M$ 的纸片。小 Bo 发现桌面上多了一个根本打不开的文件。 通过各种渠道，小 Bo 又得到了 trans(i, M) 的具体代码。
现在小 Bo 想要知道这个序列 $C$ 是什么样子的，但是 $C$ 太长了，所以他只想知道 $\sum_{i \geq 1} C_i \cdot i$，请你帮助他得到这个结果。
在附件中给出了 trans.cpp，用来描述 trans 函数。
输入格式
第一行三个整数 $N, m, t$，分别描述序列中有值的位置数量、$M$ 中不同质因子个数和操作次数。
接下来 $m$ 行，每行两个正整数 $p_i, c_i$，其中 $M = \prod_{i=1}^{m} p_i^{c_i}$。
接下来 $N$ 行，每行两个正整数 $a_i, b_i$，表示 $A_{a_i} = b_i$。
输出格式
一行，输出答案模 $1\,163\,962\,801$ 的值。
样例
样例输入一
3 1 1 3 1 2 5 5 3 6 1
样例输出一
729
样例说明
原序列 $A$ 中，有 $A_2 = 5$，$A_5 = 3$，$A_6 = 1$。
操作过后得到的序列 $B$ 为 $B_4 = 25$，$B_{10} = 30$，$B_{12} = 10$，$B_{25} = 9$，$B_{30} = 6$，$B_{36} = 1$。
$M = 3$，$M$ 中可用的约数仅有 $3$。
$4, 10, 25$ 经过 $trans$ 后数值不变，$trans(12, M) = 4$，$trans(30, M) = 10$，$trans(36, M) = 4$。
于是最后的序列 $C$ 为 $C_4 = 36, C_{10} = 36, C_{25} = 9$。
答案为 $36 \times 4 + 36 \times 10 + 9 \times 25 = 729$。
数据规模与约定
本题一共 $10$ 个测试数据，每个测试数据的分值为 $10$ 分。
每个数据的特殊性质请参见下表：
| $ID$ | $N$ | $m$ | $t$ | 特殊约定 |
|---|---|---|---|---|
| 1 | $5$ | / | $\leq 3$ | $M \leq 20, a_i \leq M$ |
| 2 | $\leq 1000$ | / | $\leq 1000$ | $M \leq 10^9$, $a_i$ 是 $M$ 的约数 |
| 3 | $\leq 1000$ | / | / | $M \leq 10^9$, $a_i$ 是 $M$ 的约数 |
| 4 | / | $\leq 200$ | / | $a_i$ 是 $M$ 的约数 |
| 5 | / | / | / | $a_i$ 是 $M$ 的约数 |
| 6 | / | $\leq 200$ | / | $c_i \leq 2$ |
| 7 | / | / | / | $c_i \leq 2$ |
| 8 | / | $\leq 200$ | / | / |
| 9 | / | / | / | / |
| 10 | / | / | / | / |
保证 $100\%$ 的数据满足：
- $1 \leq N, m \leq 100000$
- $0 \leq t \leq 10^9$
- $1 \leq a_i, b_i \leq 10^9$
- $2 \leq p_i \leq 10^9$，数据保证 $p_i, a_i$ 互不相同，且 $p_i$ 是质数
- $1 \leq c_i \leq 20$，$\prod_{i=1}^{m} c_i \leq 10^5$