题目描述

小泽生活在一条由 $N$ 个训练格组成的直线路线上。这些格子从左到右编号为 $1,2,\ldots,N$。开始时，小泽位于格子 $1$，他希望通过若干次向右跳跃到达格子 $N$。

给定 $K$ 个互不相交的整数区间 $[L_1,R_1],[L_2,R_2],\ldots,[L_K,R_K]$。这里的区间 $[l,r]$ 表示所有满足 $l\le d\le r$ 的整数 $d$ 的集合。把这些区间的并集记为 $S$。

当小泽位于格子 $i$ 时，他可以从集合 $S$ 中选择一个整数 $d$，然后跳到格子 $i+d$。如果 $i+d>N$，这次跳跃会越过训练路线的末端，因此不允许进行。

一条到达路线由每次跳跃所选的距离决定。请计算小泽从格子 $1$ 到达格子 $N$ 的不同路线数量，并输出答案对 $998244353$ 取模后的结果。

输入格式

第一行输入两个整数 $N,K$。

接下来 $K$ 行，第 $i$ 行输入两个整数 $L_i,R_i$。

输出格式

输出一个整数，表示从格子 $1$ 到格子 $N$ 的路线数对 $998244353$ 取模后的结果。

5 2
1 1
3 4

9

样例说明 #1

此时 $S=\{1,3,4\}$，四条路线为 $1\to2\to3\to4\to5$、$1\to2\to5$、$1\to4\to5$ 和 $1\to5$。

5 2
3 3
5 5

2

样例说明 #2

此时 $S=\{3,5\}$，从格子 $1$ 无法恰好到达格子 $5$，因此答案为 $0$。

5 1
1 2

12

样例说明 #3

每次可以跳 $1$ 格或 $2$ 格，到达格子 $5$ 共有 $5$ 种不同路线。

数据范围与约定

$2\le N\le2\times10^5$，$1\le K\le\min(N,10)$，$1\le L_i\le R_i\le N$。任意两个区间没有公共整数，输入中的所有数均为整数。