Правильный икосаэдр (regular icosahedron) имеет всего $20$ граней, $12$ вершин и $30$ ребер. Ниже представлен схематичный рисунок.

Циай получила правильный икосаэдр и разрезала каждую грань $3n-3$ разрезами на $n^2$ попарно конгруэнтных равносторонних треугольников. Например, на рисунке ниже показан случай $n=2$.

Теперь этот икосаэдр состоит из $20n^2$ маленьких треугольников. У Циай есть $k$ цветов. Она хочет раскрасить эти треугольники так, чтобы $a_i$ треугольников были окрашены в $i$-й цвет.

Кроме того, даже для одного и того же цвета стоимость краски может различаться. Для $i$-го цвета существует по одному виду краски с ценой $0, 1, \dots, b_i$. Краска с ценой $c$ означает, что за каждый окрашенный ею треугольник нужно заплатить $c$ единиц стоимости. Для одного и того же цвета в схеме раскраски можно произвольно использовать краски с разными ценами.

У Циай есть бюджет в $m$ единиц стоимости, и она хочет узнать для каждого $0\le j\le m$, сколько существует способов потратить ровно $j$ единиц.

Две схемы раскраски считаются одинаковыми, если одну можно получить из другой путем поворота икосаэдра. Примечание: так как Циай — профессионал, она может различать цену краски, использованной на каждом треугольнике.

Входные данные

В первой строке записаны три целых положительных числа $n, m, k$.

Далее следуют $k$ строк, в каждой из которых записаны два целых числа $a_i, b_i$.

Выходные данные

Выведите одно целое число. Пусть $f(j)$ — количество способов потратить $j$ единиц стоимости, тогда вам нужно вывести:

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

Примеры

Пример 1

Входные данные

1 100 1
20 1

Выходные данные

3554

Примечание

Данные до декодирования:

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

При этом $f(j)=f(20-j)$, а для $j>20$ выполняется $f(j)=0$.

Пример 2

Входные данные

1 100 2
9 3
11 2

Выходные данные

870

Пример 3

Входные данные

2 100 2
36 3
44 2

Выходные данные

788814413

Пример 4

Входные данные

2 100000 2
36 233
44 666

Выходные данные

953441426

Ограничения

Для всех $100\%$ данных гарантируется:

• $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$