Warning: The trans.cpp file in the attachment is unavailable, so this problem cannot be solved for the time being.
Little Bo is particularly fond of sequences. One day, he happened to obtain a sequence. This sequence is infinitely long, but uniquely, only $N$ positions in this sequence have non-zero values. Little Bo stored this sequence in his notebook. Unfortunately, one day he forgot to lock his screen. A mischievous child saw his sequence and decided to play some pranks.
The child first copied the sequence $A$ into a new sequence $B$, and then performed $t$ operations, each time assigning $B$ to be the result of the Dirichlet convolution of $A$ and $B$. Finally, the child created a new sequence $C$, added the $i$-th term of $B$ to the $trans(i, M)$-th term of $C$, and outputted the sequence $C$.
At this moment, Little Bo suddenly returned, and the child fled in a panic, leaving behind a piece of paper recording $M$. Little Bo discovered a file on his desktop that could not be opened at all. Through various channels, Little Bo obtained the specific code for trans(i, M).
Now Little Bo wants to know what this sequence $C$ looks like, but $C$ is too long, so he only wants to know $\sum_{i \geq 1} C_i \cdot i$. Please help him obtain this result.
The trans.cpp file is provided in the attachment to describe the trans function.
Input
The first line contains three integers $N, m, t$, representing the number of positions with values in the sequence, the number of distinct prime factors of $M$, and the number of operations, respectively.
The next $m$ lines each contain two positive integers $p_i, c_i$, where $M = \prod_{i=1}^{m} p_i^{c_i}$.
The next $N$ lines each contain two positive integers $a_i, b_i$, indicating that $A_{a_i} = b_i$.
Output
Output the answer modulo $1\,163\,962\,801$ on a single line.
Examples
Input 1
3 1 1 3 1 2 5 5 3 6 1
Output 1
729
Note
In the original sequence $A$, we have $A_2 = 5$, $A_5 = 3$, and $A_6 = 1$.
After the operations, the sequence $B$ becomes $B_4 = 25$, $B_{10} = 30$, $B_{12} = 10$, $B_{25} = 9$, $B_{30} = 6$, $B_{36} = 1$.
$M = 3$, and the only available divisor of $M$ is $3$.
$4, 10, 25$ remain unchanged after $trans$, while $trans(12, M) = 4$, $trans(30, M) = 10$, and $trans(36, M) = 4$.
Thus, the final sequence $C$ is $C_4 = 36, C_{10} = 36, C_{25} = 9$.
The answer is $36 \times 4 + 36 \times 10 + 9 \times 25 = 729$.
Constraints
There are 10 test cases in total, each worth 10 points.
Please refer to the table below for the special properties of each test case:
| $ID$ | $N$ | $m$ | $t$ | Special Constraints |
|---|---|---|---|---|
| 1 | $5$ | / | $\leq 3$ | $M \leq 20, a_i \leq M$ |
| 2 | $\leq 1000$ | / | $\leq 1000$ | $M \leq 10^9$, $a_i$ is a divisor of $M$ |
| 3 | $\leq 1000$ | / | / | $M \leq 10^9$, $a_i$ is a divisor of $M$ |
| 4 | / | $\leq 200$ | / | $a_i$ is a divisor of $M$ |
| 5 | / | / | / | $a_i$ is a divisor of $M$ |
| 6 | / | $\leq 200$ | / | $c_i \leq 2$ |
| 7 | / | / | / | $c_i \leq 2$ |
| 8 | / | $\leq 200$ | / | / |
| 9 | / | / | / | / |
| 10 | / | / | / | / |
It is guaranteed that $100\%$ of the data satisfies:
- $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$, it is guaranteed that all $p_i$ and $a_i$ are distinct, and $p_i$ are prime numbers
- $1 \leq c_i \leq 20$, $\prod_{i=1}^{m} c_i \leq 10^5$