有一副纸牌。牌一共有 $n$ 种，分别标有 $1, 2, \dots , 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$ 取模。
样例数据
样例 1 输入
3 3 0
样例 1 输出
10
样例 1 解释
所有方案如下：
- $\{\}$（不选任何牌）
- $\{1,1,1\}$
- $\{2,2,2\}$
- $\{3,3,3\}$
- $\{1,2,3\}$
- $\{1,1,1,2,2,2\}$
- $\{1,1,1,3,3,3\}$
- $\{2,2,2,3,3,3\}$
- $\{1,1,2,2,3,3\}$
- $\{1,1,1,2,2,2,3,3,3\}$
样例 2 输入
9 4 9 1 3 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 3
样例 2 输出
3521
子任务
对于所有数据，$1\le n\le 10^{18},0\le a_i\le C\le 1000,0\le X\le 1000$。注意 $a_i$ 和 $C$ 可能为 $0$。
- 对于 $20\%$ 的数据，$n=9,C=4$；
- 对于另外 $15\%$ 的数据，$n\le 10^5, C = 2$；
- 对于另外 $15\%$ 的数据，$X\le 5, C \le 10$；
- 对于另外 $10\%$ 的数据，$X=0$；
- 对于另外 $20\%$ 的数据，$n\le 10^5$；
- 对于余下 $20\%$ 的数据，无特殊限制。