题目描述

有 $n$ 个点和 $k$ 个区间 , 数据保证区间之间没有重合部分 。 你现在在点 $1$ , 每一次可以走 $d$ 步 ( $d$ 为给定区间中的数 ) , 求走到终点的方案数对 $998244353$ 取模的结果。

输入格式

第一行为 $n$ 与 $k$ , 含义如上

接下来 $2$ 至 $k+1$ 行为 $k$ 个区间

输出格式

输出题目要求的答案。

样例 #1

样例输入 #1

5 2
1 1
3 4

样例输出 #1

4

样例 #2

样例输入 #2

5 2
3 3
5 5

样例输出 #2

0

样例 #3

样例输入 #3

5 1
1 2

样例输出 #3

5

样例 #4

样例输入 #4

60 3
5 8
1 3
10 15

样例输出 #4

221823067

数据范围

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1 \leq\ K\ \leq\ \min(N,\ 10)$
• $1\ \leq\ L_i\ \leq\ R_i\ \leq\ N$
• 给定的区间不会相交