Ex - Random Painting 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

1 から N までの番号が振られた N 個のマスがあり、始めすべてのマスは白く塗られています。

また、箱の中に 1 から M までの番号が振られた M 個のボールが入っています。

以下の操作を、N 個のマスがすべて黒く塗られるまで繰り返します。

  1. 箱から 1 つボールを取り出す。取り出し方は完全ランダムであり、各ボールは等確率で選ばれる。
  2. 取り出したボールの番号を x として、マス L_x, L_x+1, \ldots, R_x を黒く塗る。
  3. 取り出したボールを箱に戻す。

操作回数の期待値を \text{mod } 998244353 で求めてください（注記参照）。

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この 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

出力

求めた期待値を \text{mod } 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

Score : 600 points

Problem Statement

There are N squares numbered 1 to N. Initially, all squares are painted white.

Additionally, there are M balls numbered 1 to M in a box.

We repeat the procedure below until all squares are painted black.

  1. Pick up a ball from a box uniformly at random.
  2. Let x be the index of the ball. Paint Squares L_x, L_x+1, \ldots, R_x black.
  3. Return the ball to the box.

Find the expected value of the number of times the procedure is done, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there uniquely exists an integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. You should find this R.

Constraints

  • 1 \leq N,M \leq 400
  • 1 \leq L_i \leq R_i \leq N
  • For every square i, there is an integer j such that L_j \leq i \leq R_j.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the sought expected value modulo 998244353.

Sample Input 1

3 3
1 1
1 2
2 3

Sample Output 1

499122180

The sought expected value is \frac{7}{2}.

We have 499122180 \times 2 \equiv 7\pmod{998244353}, so 499122180 should be printed.

Sample Input 2

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

Sample Output 2

10

Sample Input 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

Sample Output 3

499122193