题目描述

有 $N$ 个方块，编号为 $1$ 到 $N$。初始时，所有方块均被涂成白色。

此外，有 $M$ 个编号为 $1$ 到 $M$ 的小球在一个盒子里。

我们重复以下过程，直到所有方块均被涂成黑色。

1. 从盒子中均匀随机地取出一个小球。
2. 设 $x$ 为小球的编号。将方块 $L_x, L_{x+1}, \\ldots, R_x$ 涂成黑色。
3. 将小球放回盒子中。

计算进行该过程的次数的期望值，模 $998244353$ (见注释)。

注释

可以证明，所求的期望值总是一个有理数。此外，根据该问题的约束条件，在用两个互素的整数 $P$ 和 $Q$ 表示该值的 $\\frac{P}{Q}$ 时，可以证明存在一个唯一的整数 $R$，满足 $R \\times Q \\equiv P\\pmod{998244353}$ 且 $0 \\leq R \\lt 998244353$。您需要找到这个 $R$。

约束条件

• $1 \\leq N,M \\leq 400$
• $1 \\leq L_i \\leq R_i \\leq N$
• 对于每个方块 $i$，存在一个整数 $j$ 满足 $L_j \\leq i \\leq R_j$。
• 输入中的所有值均为整数。

输入

从标准输入读入数据，输入格式如下：

$N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$ $\\hspace{0.5cm}\\vdots$ $L_M$ $R_M$

输出

打印所求期望值取模 $998244353$ 的结果。

示例输入1

3 3
1 1
1 2
2 3

示例输出1

499122180

所求的期望值是 $\\frac{7}{2}$。

我们有 $499122180 \\times 2 \\equiv 7\\pmod{998244353}$，所以应该打印 $499122180$。

示例输入2

13 10
3 5
5 9
3 12
1 13
9 11
12 13
2 4
9 12
9 11
7 11

示例输出2

10

示例输入3

100 11
22 43
84 93
12 71
49 56
8 11
1 61
13 80
26 83
23 100
80 85
9 89

示例输出3

499122193