A62746. T4： 我要飞得更高（rocket）
题目描述
T4： 我要飞得更高（rocket）
题目描述：
你是一只毛毛虫，想要飞离地球前往空间站。空间站位于距离地球n千米的位置，在1∼n−1的每整数千米位置都有一个休息站。你最开始在地球上，距离地球0千米。为了飞到空间站，你准备了m种火箭，其中i 号火箭能够前进Li--Ri千米。为了顺利到达空间站，有如下的限制条件：
1、每种火箭可以重复使用，且没有使用顺序的限制。
2、每次前进后，如果无法到达空间站，你需要到达距离地球整数千米的位置的休息站，在休息站修整后重新使用某种火箭，直到到达空间站。
3、宇宙很大，一旦和地球的距离超出了n千米就会失联，迷失在宇宙中，因此要避免这种情况。出发前，你想算算顺利到达空间站有几种方案，因为方案数可能很多，你只需要输出方案数对998244353 取模的结果。前进次数不同或前进次数相同但是存在某一步前进距离不同，则认为两个方案不同。
输入格式：
第一行两个空格隔开的正整数表示n和m。
接下来m行，第i+1行两个空格隔开的正整数Li,Ri描述第i个火箭的能力。
输出格式：
输出一行一个非负整数表示方案数对998244353取模的结果。
输入输出样例
输入1：
3 2
1 3
2 2
输出1：
4
输入2：
5 1
3 4
输出2：
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≤n≤10^5,1≤m≤200,1≤Li ≤Ri≤n。