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$ 分。

每个数据的特殊性质请参见下表：

保证 $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$