正二十面体（regular icosahedron） 总共有 $20$ 个面，$12$ 个顶点，$30$ 条棱。这是一张示意图。

岐艾拿到了一个正二十面体，她将每个面都用 $3n-3$ 刀切割成了 $n^2$ 个彼此全等的等边三角形。例如下图是一个 $n=2$ 的情况。

现在这个正 $20$ 面体总共有了 $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$。

输出格式

输出一个整数，设 $j$ 元钱对应的方案数是 $f(j)$，那么你只需要输出

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

样例数据

样例 1 输入

1 100 1
20 1

样例 1 输出

3554

样例 1 解释

解码前的数据有：

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

样例 2 输出

870

样例 3 输入

2 100 2
36 3
44 2

样例 3 输出

788814413

样例 4 输入

2 100000 2
36 233
44 666

样例 4 输出

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$