4206. [HA CSP-X 2025]我要飞得更高

【题目背景】

你是一只毛毛虫，想要飞离地球前往空间站。

【题目描述】

空间站位于距离地球 $n$ 千米的位置，在 $1\sim n-1$ 的每整数千米位置都有一个休息站。你最开始在地球上，距离地球 0 千米。为了飞到空间站，你准备了 $m$ 种火箭，其中

$i$ 号火箭能够前进 $L_i\sim R_i$ 千米。为了顺利到达空间站，有如下的限制条件：

1. 每种火箭可以重复使用，且没有使用顺序的限制。

2. 每次前进后，如果无法到达空间站，你需要到达距离地球整数千米的位置的休息

站，在休息站修整后重新使用某种火箭，直到到达空间站。

3. 宇宙很大，一旦和地球的距离超出了 $n$ 千米就会失联，迷失在宇宙中，因此要避免这种情况。

出发前，你想算算顺利到达空间站有几种方案，因为方案数可能很多，你只需要输出方案数对 $998244353$ 取模的结果。前进次数不同或前进次数相同但是存在某一步前进

距离不同，则认为两个方案不同。

【输入格式】

第一行两个空格隔开的正整数表示 $n$ 和 $m$。

接下来 $m$ 行，第 $i + 1$ 行两个空格隔开的正整数 $L_i\sim R_i$ 描述第 $i$ 个火箭的能力。

【输出格式】

输出一行一个非负整数表示方案数对 $998244353$ 取模的结果。

【样例1输入】

3 2
1 3
2 2

【样例1输出】

4

【样例1说明】

第一个火箭可以让你前进 $1$、$2$ 或 $3$ 千米，第二个火箭可以让你前进 $2$ 千米。

到达 $1$ 千米位置的休息站的方案只有一个，就是从地球前进 $1$ 千米。到达 $2$ 千米位置的休息站的方案有两个，一个是前进 $2$ 千米，一个是前进 $1$ 千米再前进 $1$ 千米。到达 $3$ 千米的空间站的方案有四个，分别是前进 $3$、前进 $2$ 再前进 $1$、前进 $1$ 前进 $2$、前进 $1$ 前进 $1$ 再前进 $1$。

询问你到达 $3$ 千米的空间站的方案数，所以输出 $4$。

【样例2输入】

5 1
3 4

【样例2输出】

0

【样例2说明】

只有一种火箭，可以让你前进 $3$ 或 $4$ 千米。

到达 $3$ 千米和 $4$ 千米位置的休息站的方案都是 $1$。无论怎么前进都只能停在中间或者距离超出 $5$ 千米，无法顺利到达空间站，因此到达空间站的方案为 $0$。

【数据规模与约定】

对于所有数据，$1\leq n\leq 10^5,1\leq m\leq 200,1\leq L_i\leq R_i\leq n$。每个测试点的具体限制见下表：

【来源】

2025 年河南省青少年程序设计能力认证