AT_abc242_h [ABC242Ex] Random Painting

有 $N$ 个编号为 $1$ 到 $N$ 的格子，开始时所有格子都是白色的。 同时，有 $M$ 个编号为 $1$ 到 $M$ 的球放在箱子里。 重复以下操作，直到所有 $N$ 个格子都被涂成黑色为止： 1. 从箱子中随机取出一个球。每个球被取出的概率相等。 2. 设取出的球的编号为 $x$，则将格子 $L_x, L_x+1, \ldots, R_x$ 全部涂成黑色。 3. 将取出的球放回箱子。 请计算将所有格子涂黑所需操作次数的期望值，并对 $998244353$ 取模输出（见注记）。

输入通过标准输入给出，格式如下： > $N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$ > $\hspace{0.5cm}\vdots$ > $L_M$ $R_M$

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

### 注记 可以证明，所求的期望值一定是有理数。在本题的约束下，若用互质的两个整数 $P$、$Q$ 表示为 $\frac{P}{Q}$，则一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 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$ - 所有输入均为整数 ### 样例解释 1 所求期望值为 $\frac{7}{2}$。$499122180 \times 2 \equiv 7 \pmod{998244353}$，所以输出 $499122180$。 由 ChatGPT 4.1 翻译