分数: 400 点
问题陈述
有 N 单元格排列成行,编号 1, 2, \ldots, N 从左到右。
Tak 生活在这些细胞中,目前在 Cell 上 1。他正在尝试联系 Cell N 通过使用下面描述的过程。
给你一个整数 K 小于或等于 10,和 K 非相交线段 [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]。 让 S 是这些的并集 K 段。 这里,该段 [l, r] 表示由所有整数组成的集合 i 满足 l \leq i \leq r.
- 当您使用手机时 i,选择一个整数 d 来自 S 并移至单元格 i + d。你不能移出牢房。
为了帮助 Tak,找出前往 Cell 的方法 N,模数 998244353.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq \min(N, 10)
- 1 \leq L_i \leq R_i \leq N
- [L_i, R_i] 和 [L_j, R_j] 不相交 (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K L_1 R_1 L_2 R_2 : L_K R_K
输出
打印 Tak 从 Cell 出发的路数 1 到单元格 N,模数 998244353.
示例输入 1
5 2 1 1 3 4
示例输出 1
4
该套 S 是段的并集 [1, 1] 和段 [3, 4],因此 S = \{ 1, 3, 4 \} 成立。
有 4 到达 Cell 的可能方式 5:
- 1 \to 2 \to 3 \to 4 \to 5,
- 1 \to 2 \to 5,
- 1 \to 4 \to 5 和
- 1 \to 5.
示例输入 2
5 2 3 3 5 5
示例输出 2
0
因为 S = \{ 3, 5 \} 成立,您无法到达单元格 5。 打印 0.
示例输入 3
5 1 1 2
示例输出 3
5
示例输入 4
60 3 5 8 1 3 10 15
示例输出 4
221823067
请注意,您必须打印答案模数 998244353.