题目描述
有一副纸牌。牌一共有 n 种,分别标有 1,2,…,n,每种有 C 张。故这副牌共有 nC 张。
三张连号的牌(i,i+1,i+2)或三张相同的牌 (i,i,i) 可以组成一叠。如果一组牌可以分成若干(包括零)叠,就称其为一组王牌。
你从牌堆中摸了一些初始牌。现在你想再挑出一些牌组成一组王牌,请问有多少种可能组成的王牌呢?答案对 998244353 取模。
两组牌相同当且仅当它们含有的每一种牌数量都相同。
输入格式
第 1 行两个整数 n,C 表示牌的种类数和每种的张数;
第 2 行一个整数 X 表示初始牌的种类数;
接下来 X 行每行两个整数 ki,ai,表示初始牌中有 ai 张 ki 号牌。每行的 ki 依次递增。
输出格式
输出 1 行 1 个自然数表示答案,对 998244353 取模。
样例 1
3 3
0
10
所有方案如下:
-
{}(不选任何牌)
-
{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}
9 4
9
1 3
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 3
3521
见附加文件。
数据范围与提示
对于所有数据,1≤n≤1018,0≤ai≤C≤1000,0≤X≤1000。注意 ai 和 C 可能为 0。
- 对于 20% 的数据,n=9,C=4;
- 对于另外 15% 的数据,n≤105,C=2;
- 对于另外 15% 的数据,X≤5,C≤10;
- 对于另外 10% 的数据,X=0;
- 对于另外 20% 的数据,n≤105;
- 对于余下 20% 的数据,无特殊限制。