题目描述

有 $N$ 个按顺序排列的单元格，编号为 $1, 2, \\ldots, N$。

Tak 生活在这些单元格中，目前在单元格 $1$。他试图通过以下步骤到达单元格 $N$。

给定一个整数 $K$，它小于或等于 $10$，以及 $K$ 个不相交的线段 \[L_1, R_1\], \[L_2, R_2\], \\ldots, \[L_K, R_K\]。令 $S$ 是这 $K$ 个线段的并集。这里，线段 \[l, r\] 表示满足 $l \\leq i \\leq r$ 的所有整数 $i$ 的集合。

• 当你在单元格 $i$ 时，从 $S$ 中选择一个整数 $d$，然后移动到单元格 $i + d$。你不能移出单元格。

为了帮助 Tak，计算从单元格 $1$ 到单元格 $N$ 的方式数量，取模 $998244353$。

约束条件

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq K \\leq \\min(N, 10)$
• $1 \\leq L_i \\leq R_i \\leq N$
• \[L_i, R_i\] 和 \[L_j, R_j\] 不相交 ($i \\neq j$)
• 输入中的所有值都为整数。

---

输入

输入以以下格式从标准输入中给出：

$N$ $K$ $L_1$ $R_1$ $L_2$ $R_2$ $:$ $L_K$ $R_K$

输出

输出从单元格 $1$ 到单元格 $N$ 有多少种方式，取模 $998244353$。

---

示例输入 1

5 2
1 1
3 4

示例输出 1

4

集合 $S$ 是线段 \[1, 1\] 和线段 \[3, 4\] 的并集，因此 $S = \\{ 1, 3, 4 \\}$。

有 $4$ 种可能的方式到达单元格 $5$：

• $1 \\to 2 \\to 3 \\to 4 \\to 5$，
• $1 \\to 2 \\to 5$，
• $1 \\to 4 \\to 5$ 和
• $1 \\to 5$。

---

示例输入 2

5 2
3 3
5 5

示例输出 2

0

因为 $S = \\{ 3, 5 \\}$，所以无法到达单元格 $5$。输出 $0$。

---

示例输入 3

5 1
1 2

示例输出 3

5

---

示例输入 4

60 3
5 8
1 3
10 15

示例输出 4

221823067

请注意需要将答案取模 $998244353$。