题目描述

有一副纸牌。牌一共有 $n$ 种，分别标有 $1,2,...,n$ ，每种有 $C$ 张。故这副牌总共有 $nC$ 张。

三张连号的牌 $(i,i+1,i+2)$ 或三张相同的牌 $(i,i,i)$ 可以组成一叠。如果一组牌可以分成若干（包括零）叠，就称其为一组王牌。

你从牌堆中摸了一些初始牌。现在你想挑出一些牌组成一组王牌，请问有多少种可能组成的王牌呢？答案对 $998244353$ 取模。

两组牌相同当且仅当它们含有的每一种牌数量都相同。

输入格式

第 $1$ 行两个整数 $n,C$ 表示牌的种类数和每种的张数；

第 $2$ 行一个整数 $X$ 表示初始牌的种类数；

接下来 $X$ 行每行两个整数 $k_i,a_i$ ，表示初始牌中有 $a_i$ 张 $k_i$ 号牌。每行的 $k_i$ 依次递增。

输出格式

输出 $1$ 行 $1$ 个自然数表示答案，对 $998244353$ 取模。

3 3
0

10

9 4
9
1 3
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 3

3521

提示

样例解释1

所有方案如下：

1. $\{\}$ （不选任何牌）
2. $\{1,1,1\}$
3. $\{2,2,2\}$
4. $\{3,3,3\}$
5. $\{1,2,3\}$
6. $\{1,1,1,2,2,2\}$
7. $\{1,1,1,3,3,3\}$
8. $\{2,2,2,3,3,3\}$
9. $\{1,1,2,2,3,3\}$
10. $\{1,1,1,2,2,2,3,3,3\}$

数据范围

对于所有数据， $1\leq n\leq 10^{18},0\leq a_i\leq C\leq 1000,0\leq X\leq 1000$ 。注意 $a_i$ 和 $C$ 可能为 $0$ 。

• 对于 $20\%$ 的数据， $n=9,C=4$ 。
• 对于另外 $15\%$ 的数据， $n\leq 10^5,C=2$ 。
• 对于另外 $15\%$ 的数据， $X\leq 5,C\leq 10$ 。
• 对于另外 $10\%$ 的数据， $X=0$ 。
• 对于另外 $20\%$ 的数据， $n\leq 10^5$ 。
• 对于余下 $20\%$ 的数据，无特殊限制。