注意

本题需要文件读写

输入文件名 rocket.in

输出文件名 rocket.out

Description

你是一只毛毛虫，想要飞离地球前往空间站。 空间站位于距离地球 $n$ 千米的位置，在 $1$ ∼ $n − 1$ 的每整数千米位置都有一个休息站。你最开始在地球上，距离地球 0 千米。为了飞到空间站，你准备了 $m$ 种火箭，其中i 号火箭能够前进 $L_i$ ∼ $R_i$ 千米。

为了顺利到达空间站，有如下的限制条件：

1、每种火箭可以重复使用，且没有使用顺序的限制。

2、每次前进后，如果无法到达空间站，你需要到达距离地球整数千米的位置的休息站，在休息站修整后重新使用某种火箭，直到到达空间站。

3、宇宙很大，一旦和地球的距离超出了 $n$ 千米就会失联，迷失在宇宙中，因此要避免这种情况。

出发前，你想算算顺利到达空间站有几种方案，因为方案数可能很多，你只需要输出方案数对 $998244353$ 取模的结果。前进次数不同或前进次数相同但是存在某一步前进距离不同，则认为两个方案不同。

Format

Input

从文件 rocket.in 中读入数据。 第一行两个空格隔开的正整数表示 $n$ 和 $m$。 接下来 $m$ 行，第 $i + 1$ 行两个空格隔开的正整数 $L_i$ , $R_i$ 描述第 $i$ 个火箭的能力。

对于所有数据，1 ≤ $n$ ≤ $10^5$, 1 ≤ $m$ ≤ 200, 1 ≤ $L_i$ ≤ $R_i$ ≤ $n$。

Output

输出到文件 rocket.out 中。 输出一行一个非负整数表示方案数对 $998244353$ 取模的结果。

Samples

3 2
1 3
2 2

4

解释

第一个火箭可以让你前进 1、2 或 3 千米，第二个火箭可以让你前进 2 千米。 到达 1 千米位置的休息站的方案只有一个，就是从地球前进 1 千米。到达 2 千米位置的休息站的方案有两个，一个是前进 2 千米，一个是前进 1 千米再前进 1 千米。到达3 千米的空间站的方案有四个，分别是前进 3、前进 2 再前进 1、前进 1 前进 2、前进 1、前进 1 再前进 1。 询问你到达 3 千米的空间站的方案数，所以输出 4。

5 1
3 4

0

解释

只有一种火箭，可以让你前进 3 或 4 千米。 到达 3 千米和 4 千米位置的休息站的方案都是 1。无论怎么前进都只能停在中间或者距离超出 5 千米，无法顺利到达空间站，因此到达空间站的方案为 0。