跳跃

题目描述

有一个由排成一列的 $N$ 个格子组成的棋盘,格子从左到右依次编号为 $1, 2, \ldots, N$。

高桥君住在这个棋盘上,他现在在格子 $1$,打算按后述方法反复移动前往格子 $N$。

给定不超过 $10$ 的整数 $K$,以及互不重叠的 $K$ 个区间 $[L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K]$,把这些区间的并集记为 $S$。其中,区间 $[l, r]$ 表示由 $l$ 以上 $r$ 以下的整数组成的集合。

• 在格子 $i$ 时,从 $S$ 中选一个整数(记为 $d$),移动到格子 $i + d$。但是,不允许进行移出棋盘的移动。

请为高桥君求出到格子 $N$ 的方法数除以 $998244353$ 的余数。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$L_1$ $R_1$
$L_2$ $R_2$
$:$
$L_K$ $R_K$

输出格式

输出高桥君从格子 $1$ 到格子 $N$ 的方法数除以 $998244353$ 的余数。

样例

5 2
1 1
3 4

4

集合 $S$ 是区间 $[1, 1]$ 和区间 $[3, 4]$ 的并集,$S = \{ 1, 3, 4 \}$。

移动到格子 $5$ 的方法有以下 $4$ 种:

• 按格子 $1, 2, 3, 4, 5$ 的顺序移动。
• 按格子 $1, 2, 5$ 的顺序移动。
• 按格子 $1, 4, 5$ 的顺序移动。
• 按格子 $1, 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

注意要输出除以 $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$)
• 输入均为整数