随机涂色

题目描述

有 $N$ 个方格,编号为 $1$ 到 $N$。初始时所有方格都是白色的。

此外,盒子里有 $M$ 个球,编号为 $1$ 到 $M$。

我们重复下面的操作,直到所有方格都变成黑色。

• 从盒子里均匀随机取出一个球。
• 设取出的球的编号为 $x$。将方格 $L_x, L_x+1, \ldots, R_x$ 涂成黑色。
• 将球放回盒子。

求操作次数的期望值,对 $998244353$ 取模(参见「提示」)。

输入格式

输入按以下格式从标准输入给出:

N M
L_1 R_1
L_2 R_2
⋮
L_M R_M

输出格式

输出所求的期望值对 $998244353$ 取模后的结果。

样例

3 3
1 1
1 2
2 3

499122180

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

因为 $499122180 \times 2 \equiv 7\pmod{998244353}$,所以应输出 $499122180$。

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

10

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

499122193

数据范围

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

提示

可以证明,所求的期望值总是有理数。此外,在本问题的约束下,当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时,可以证明存在唯一的整数 $R$,满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。你需要求出这个 $R$。