背景

2025 年河南省青少年程序设计能力认证 第二轮认证（小学组） 第四题

PDF 首页注意事项：输入文件中可能存在行末空格，请选手使用更完善的读入方式（例如 scanf 函数）避免出错。

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

题目描述

空间站位于距离地球 $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, R_i$ 描述第 $i$ 个火箭的能力。

输出格式

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

3 2
1 3
2 2

4

5 1
3 4

0

提示

【样例解释 #1】

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

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

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

【样例解释 #2】

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

【测试点约束】

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

::cute-table{tuack} | 测试点编号 | 约束 | | :--: | :--: | | $1\sim 3$ | $m=1,\ L_1=R_1$ | | $4\sim 5$ | $L_i=R_i$ | | $6\sim 9$ | $1\le n\le 1000$ | | $10\sim 13$ | 对于任意 $1\le i<m$，保证 $R_i<L_{i+1}$ | | $14\sim 20$ | 没有其他限制 |