← 返回题目列表

AtCoder · abc179_d

D. 跃德

中文机器翻译题面 查看原题

分数: 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.