题目描述

有一副纸牌。牌一共有 $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$ 取模。

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\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\%$ 的数据，无特殊限制。