D - 跳跃的 Tak

得分：400分

题目描述

有 $N$ 个按顺序排列的单元格，编号从 $1$ 到 $N$，从左到右。

Tak住在这些单元格中，目前位于第 $1$ 个单元格。他试图通过以下操作到达第 $N$ 个单元格。

给定一个整数 $K$，它小于等于 $10$，和 $K$ 个不相交的段 $[L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]$。 令 $S$ 为这 $K$ 个段的并集。 这里，段 $[l, r]$ 表示所有满足 $l \leq i \leq r$ 的整数 $i$ 的集合。

• 当你位于第 $i$ 个单元格时，从 $S$ 中选择一个整数 $d$ 并移动到第 $i + d$ 个单元格。你不能移出单元格。

为了帮助Tak，找到从第 $1$ 个单元格到第 $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从第 $1$ 个单元格到第 $N$ 个单元格的方法数，取模 $998244353$。

5 2
1 1
3 4

4

集合 $S$ 是段 $[1, 1]$ 和段 $[3, 4]$ 的并集，因此 $S = \{ 1, 3, 4 \}$。

有 $4$ 种方式可以到达第 $5$ 个单元格：

• $1 \to 2 \to 3 \to 4 \to 5$
• $1 \to 2 \to 5$
• $1 \to 4 \to 5$
• $1 \to 5$

5 2
3 3
5 5

0

因为 $S = \{ 3, 5 \}$，无法到达第 $5$ 个单元格。 输出 $0$。

5 1
1 2

5

60 3
5 8
1 3
10 15

221823067