Regularny dwudziestościan (regular icosahedron) ma łącznie $20$ ścian, $12$ wierzchołków i $30$ krawędzi. Poniżej znajduje się rysunek poglądowy.

Qiai otrzymała regularny dwudziestościan i każdą jego ścianę pocięła za pomocą $3n-3$ cięć na $n^2$ przystających trójkątów równobocznych. Na przykład poniższy rysunek przedstawia przypadek dla $n=2$.

Teraz ten dwudziestościan ma łącznie $20n^2$ małych trójkątów, a Qiai dysponuje $k$ kolorami. Chce ona pomalować te trójkąty tak, aby $a_i$ trójkątów było pomalowanych kolorem $i$.

Ponadto, nawet w obrębie tego samego koloru, ceny farb mogą się różnić. Dla koloru $i$ dostępna jest po jednej farbie o cenach $0, 1, \dots, b_i$. Farba o cenie $c$ oznacza, że pomalowanie nią jednego pola kosztuje $c$ jednostek waluty. W ramach tego samego koloru można dowolnie używać farb o różnych cenach w schemacie malowania.

Qiai ma budżet $m$ jednostek waluty, więc chce wiedzieć, dla każdego $0\le j\le m$, ile istnieje sposobów na wydanie dokładnie $j$ jednostek waluty.

Jeśli dwa schematy malowania można przekształcić jeden w drugi poprzez obrót dwudziestościanu, uważa się je za ten sam schemat. Uwaga: ponieważ Qiai jest profesjonalistką, potrafi rozróżnić cenę farby użytej na każdym polu.

Wejście

Pierwsza linia zawiera trzy liczby całkowite dodatnie $n, m, k$.

Następnie $k$ linii, z których każda zawiera dwie liczby całkowite $a_i, b_i$.

Wyjście

Wyprowadź jedną liczbę całkowitą. Niech $f(j)$ oznacza liczbę sposobów na wydanie $j$ jednostek waluty. Należy wyprowadzić:

$$ \bigoplus_{j=0}^m ((f(j) \bmod 998244353) + j) $$

Przykład

Przykład 1 Wejście

1 100 1
20 1

Przykład 1 Wyjście

3554

Uwagi

Dane przed dekodowaniem:

$$ f(0,\dots,10) = [1, 1, 6, 21, 96, 262, 681, 1302, 2157, 2806, 3158] $$

Ponadto $f(j)=f(20-j)$, a dla $j>20$ zachodzi $f(j)=0$.

Przykład 2 Wejście

1 100 2
9 3
11 2

Przykład 2 Wyjście

870

Przykład 3 Wejście

2 100 2
36 3
44 2

Przykład 3 Wyjście

788814413

Przykład 4 Wejście

2 100000 2
36 233
44 666

Przykład 4 Wyjście

953441426

Ograniczenia

Dla $100\%$ danych wejściowych:

• $1\le n\le 7\times 10^3$
• $0\le m\le 5\times 10^6$
• $1\le k\le 5$
• $1\le a_i$
• $\sum_i a_i = 20n^2$
• $0\le b_i\le m$