跑道
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
有一条由 N 个格子组成的直线跑道，从左到右编号为 1 到 N。
小南从第 1 个格子出发，目标是到达第 N 个格子。
已知可以使用的跳跃步长由 K 个互不相交的整数区间给出：[L_1, R_1], [L_2, R_2], …, [L_K, R_K]。把这些区间并在一起记作集合 S。其中区间 [l, r] 表示所有满足 l ≤ x ≤ r 的整数 x。
- 当小南位于第
i个格子时，可以任选一个d ∈ S，跳到第i + d个格子；不能跳出编号范围1..N。
请计算小南从第 1 个格子到达第 N 个格子的不同方案数，并将答案对 998244353 取模。
输入格式
按以下格式从标准输入读入：
N K
L_1 R_1
L_2 R_2
…
L_K R_K
输出格式
输出一个整数，表示从第 1 个格子到达第 N 个格子的方案数（对 998244353 取模）。
数据范围与子任务
- 子任务 1（20%）：
N ≤ 1,000，K ≤ 3 - 子任务 2（30%）：
N ≤ 50,000，K ≤ 6 - 子任务 3（50%）：
N ≤ 200,000，K ≤ 10
输入输出样例 #1
输入：
5 2
1 1
3 4
输出：
4
输入输出样例 #2
输入：
5 2
3 3
5 5
输出：
0
输入输出样例 #3
输入：
5 1
1 2
输出：
5
输入输出样例 #4
输入：
60 3
5 8
1 3
10 15
输出：
221823067
限制条件
2 ≤ N ≤ 2 × 10^51 ≤ K ≤ min(N, 10)1 ≤ L_i ≤ R_i ≤ N- 区间两两互不相交（对任意
i ≠ j，[L_i, R_i] ∩ [L_j, R_j] = ∅） - 所有输入均为整数
