A96805.跳格子

有一个由 $N$ 个格子组成的格子列，这些格子从左到右依次编号为 $1,2,\dots,N$。

住在这个格子上的 Welcome24ever 现在在第 $1$ 个格子，他想通过下面描述的方法不断移动，最终到达第 $N$ 个格子。

给定一个不超过 $10$ 的整数 $K$，以及 $K$ 个互不相交的区间 $[L_1,R_1],[L_2,R_2],\dots,[L_K,R_K]$，这些区间的并集记为集合 $S$。
这里区间 $[l,r]$ 表示所有满足 $l \le x \le r$ 的整数 $x$ 的集合。

• 当 Welcome24ever 在第 $i$ 个格子时，他可以从集合 $S$ 中任选一个整数 $d$，然后移动到第 $i+d$ 个格子。
• 如果 $i+d$ 超出了 $1$ 到 $N$ 的范围，则不能进行这样的移动。

请你计算，从第 $1$ 个格子到达第 $N$ 个格子的不同移动方案数。答案对 $998244353$ 取模。

输入的第一行包含两个整数 $N,K$。

接下来的 $K$ 行中，第 $j$ 行包含两个整数 $L_j,R_j$。

输出一个整数，表示从第 $1$ 个格子到达第 $N$ 个格子的方案数，对 $998244353$ 取模。

数据范围

• $2 \le N \le 2 \times 10^5$；
• $1 \le K \le \min(N,10)$；
• 对所有 $j$，有 $1 \le L_j \le R_j \le N$；
• 对所有 $i \ne j$，区间 $[L_i,R_i]$ 与 $[L_j,R_j]$ 互不相交；
• 输入中的所有数都是整数。

样例解释 1

此时集合 $S$ 为区间 $[1,1]$ 和 $[3,4]$ 的并集：

$$S = \{1,3,4\}.$$

从第 $1$ 个格子出发，到达第 $5$ 个格子的方案共有 $4$ 种：

1. 依次到达格子 $1,2,3,4,5$（每次移动 $1$ 格）；
2. 依次到达格子 $1,2,5$（先移动 $1$ 格，再移动 $3$ 格）；
3. 依次到达格子 $1,4,5$（先移动 $3$ 格，再移动 $1$ 格）；
4. 依次到达格子 $1,5$（直接移动 $4$ 格）。

因此答案为 $4$。

样例解释 2

此时集合 $S = \{3,5\}$。
从第 $1$ 个格子出发：

• 第一次移动可以到格子 $4$（加 $3$）或者格子 $6$（加 $5$，非法）；
• 从格子 $4$ 再移动 $3$ 或 $5$ 都会超出范围。

所以无法到达第 $5$ 个格子，方案数为 $0$。

样例解释 3

此时集合 $S = \{1,2\}$。
可以验证所有到达格子 $5$ 的方案对应于将数字 $1$ 和 $2$ 相加得到和为 $4$ 的不同拆分方式，一共有 $5$ 种：

• $1+1+1+1$；
• $1+1+2$；
• $1+2+1$；
• $2+1+1$；
• $2+2$。

因此答案为 $5$。