Mały Bo szczególnie lubi ciągi liczbowe. Pewnego dnia przypadkiem wszedł w posiadanie ciągu, który jest nieskończenie długi, ale co ciekawe, tylko w $N$ miejscach posiada niezerowe wartości. Mały Bo zapisał ten ciąg w swoim notatniku. Niestety, pewnego dnia zapomniał zablokować ekran. Pewne niegrzeczne dziecko zobaczyło jego ciąg i postanowiło zrobić psikusa.

Dziecko najpierw skopiowało ciąg $A$ do nowego ciągu $B$, a następnie wykonało $t$ operacji, w każdej z nich przypisując $B$ wynik splotu Dirichleta ciągów $A$ i $B$. Na koniec dziecko utworzyło nowy ciąg $C$, dodając $i$-ty wyraz ciągu $B$ do wyrazu o indeksie $trans(i, M)$ w ciągu $C$, a następnie wypisało ciąg $C$.

W tym momencie Mały Bo nagle wrócił, a dziecko uciekło w popłochu, gubiąc w pośpiechu kartkę z zapisaną wartością $M$. Mały Bo odkrył na pulpicie plik, którego nie dało się otworzyć. Dzięki różnym kanałom Mały Bo zdobył kod funkcji trans(i, M).

Teraz Mały Bo chce wiedzieć, jak wygląda ciąg $C$, ale jest on zbyt długi, więc chce jedynie poznać wartość $\sum_{i \geq 1} C_i \cdot i$. Pomóż mu uzyskać ten wynik.

W załączniku znajduje się plik trans.cpp, który opisuje funkcję trans.

Wejście

Pierwsza linia zawiera trzy liczby całkowite $N, m, t$, określające odpowiednio liczbę niezerowych elementów w ciągu, liczbę różnych czynników pierwszych liczby $M$ oraz liczbę operacji.

Następnie $m$ linii, każda zawiera dwie liczby całkowite dodatnie $p_i, c_i$, gdzie $M = \prod_{i=1}^{m} p_i^{c_i}$.

Następnie $N$ linii, każda zawiera dwie liczby całkowite dodatnie $a_i, b_i$, oznaczające, że $A_{a_i} = b_i$.

Wyjście

Wypisz w jednej linii wynik modulo $1\,163\,962\,801$.

Przykład

Przykład 1

3 1 1
3 1
2 5
5 3
6 1

Wyjście 1

729

Uwagi

W oryginalnym ciągu $A$ mamy $A_2 = 5$, $A_5 = 3$, $A_6 = 1$.

Po operacjach otrzymany ciąg $B$ to $B_4 = 25$, $B_{10} = 30$, $B_{12} = 10$, $B_{25} = 9$, $B_{30} = 6$, $B_{36} = 1$.

$M = 3$, jedynym dostępnym dzielnikiem $M$ jest $3$.

Wartości $4, 10, 25$ po przekształceniu przez $trans$ pozostają bez zmian, $trans(12, M) = 4$, $trans(30, M) = 10$, $trans(36, M) = 4$.

Zatem końcowy ciąg $C$ to $C_4 = 36, C_{10} = 36, C_{25} = 9$.

Wynik to $36 \times 4 + 36 \times 10 + 9 \times 25 = 729$.

Ograniczenia

Zadanie składa się z 10 zestawów danych testowych, każdy warty 10 punktów.

Szczegółowe właściwości każdego zestawu danych przedstawiono w poniższej tabeli:

Gwarantuje się, że 100% danych spełnia:

• $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$, dane gwarantują, że $p_i, a_i$ są parami różne, a $p_i$ są liczbami pierwszymi
• $1 \leq c_i \leq 20$, $\prod_{i=1}^{m} c_i \leq 10^5$