← 返回题目列表

AtCoder · abc242_h

Ex. 随机绘画

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 编号的方块 1 to N。最初,所有方块都漆成白色。

此外,还有 M 球编号 1 to 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.


示例输入 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