#3098. 「SNOI2019」纸牌

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一副纸牌。牌一共有 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. \{\} (不选任何牌)

  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\}

样例输入 2

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

样例输出 2

3521

样例 3

见附加文件。

数据范围与提示

对于所有数据, 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\% 的数据,无特殊限制。