#P5371. [SNOI2019] 纸牌

[SNOI2019] 纸牌

题目描述

有一副纸牌。牌一共有 nn 种,分别标有 1,2,...,n1,2,...,n ,每种有 CC 张。故这副牌总共有 nCnC 张。

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

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

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

输入格式

11 行两个整数 n,Cn,C 表示牌的种类数和每种的张数;

22 行一个整数 XX 表示初始牌的种类数;

接下来 XX 行每行两个整数 ki,aik_i,a_i ,表示初始牌中有 aia_ikik_i 号牌。每行的 kik_i 依次递增。

输出格式

输出 1111 个自然数表示答案,对 998244353998244353 取模。

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}\{1,1,1\}
  3. {2,2,2}\{2,2,2\}
  4. {3,3,3}\{3,3,3\}
  5. {1,2,3}\{1,2,3\}
  6. {1,1,1,2,2,2}\{1,1,1,2,2,2\}
  7. {1,1,1,3,3,3}\{1,1,1,3,3,3\}
  8. {2,2,2,3,3,3}\{2,2,2,3,3,3\}
  9. {1,1,2,2,3,3}\{1,1,2,2,3,3\}
  10. {1,1,1,2,2,2,3,3,3}\{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$ 。注意 aia_iCC 可能为 00

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