B. 跳格子

题目描述

有 $N$ 个格子排成一排，你可以从 $1$ 号格子出发向右跳。 给定 $K$ 个区间 $[L_i, R_i]$，每一次可以走 $d$ 步（$L_i \le d \le R_i$），求走到终点 $N$ 的方案数，对 $998244353$ 取模的结果。

样例1解释： 单步可以跳的步长为 $1, 3, 4$ $4$ 种方案的路径序列为 $1,2,3,4,5$ $1,4,5$ $1,2,5$ $1,5$

输入格式

第一行：$N\ K$ 接下来 $K$ 行，每行两个整数 $L_i\ R_i$

输出格式

输出答案，对 $998244353$ 取模

样例

输入样例 #1

5 2
1 1
3 4

输出样例 #1

4

输入样例 #2

5 2
3 3
5 5

输出样例 #2

0

输入样例 #3

5 1
1 2

输出样例 #3

5

输入样例 #4

60 3
5 8
1 3
10 15

输出样例 #4

221823067

数据范围与提示

• $2 \le N \le 2 \times 10^5$
• $1 \le K \le \min(N, 10)$
• $1 < L_i < R_i < N$
• 不同区间没有交集