Сяо Бо очень любит числовые последовательности. Однажды он случайно получил бесконечно длинную последовательность, в которой, однако, только $N$ элементов имеют ненулевые значения. Сяо Бо сохранил эту последовательность в своем блокноте. К несчастью, однажды он забыл заблокировать экран. Хулиган увидел его последовательность и решил устроить розыгрыш.
Хулиган сначала скопировал последовательность $A$ в новую последовательность $B$, а затем выполнил $t$ операций, каждый раз заменяя $B$ на результат дирихле-свертки последовательностей $A$ и $B$. Наконец, хулиган создал новую последовательность $C$, прибавил $i$-й элемент $B$ к элементу $C$ с индексом $trans(i, M)$ и вывел последовательность $C$.
В этот момент Сяо Бо внезапно вернулся, и хулиган в спешке убежал, обронив листок с числом $M$. Сяо Бо обнаружил на рабочем столе файл, который невозможно открыть. С помощью различных каналов Сяо Бо получил исходный код функции trans(i, M).
Теперь Сяо Бо хочет узнать, как выглядит последовательность $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$.
Примеры
Пример 1
3 1 1 3 1 2 5 5 3 6 1
Выходные данные 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$ — различны
- $1 \leq c_i \leq 20$, $\prod_{i=1}^{m} c_i \leq 10^5$