当前没有测试数据。

Ex - 随机绘画

得分：$600$ 分

题目描述

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

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

我们重复以下步骤，直到所有方块都被涂成黑色：

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

求完成这个过程的次数的期望值，结果对 $998244353$ 取模（见 注释）。

注释

可以证明所求的期望值总是一个有理数。此外，在此问题的约束条件下，当将该值表示为 $\frac{P}{Q}$，其中 $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$ 取模后输出。

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