[ABC242Ex] Random Painting

有 $m$ 个小球，一开始标号为 $1\sim m$，每个对应一个区间 $[L_i,R_i]$。有 $n$ 个方块，标号 $1\sim n$，初始时无色。重复以下步骤直到所有的方块都被涂色： 1. 随机拿出一个小球 $i$ 2. 将 $[L_i,R_i]$ 涂色 3. 将小球放回去 问期望进行步骤的次数。 - $1\le n,m\le 400,1\le L_i,R_i\le n$

[problemUrl]: https://atcoder.jp/contests/abc242/tasks/abc242_h $ 1 $ から $ N $ までの番号が振られた $ N $ 個のマスがあり、始めすべてのマスは白く塗られています。 また、箱の中に $ 1 $ から $ M $ までの番号が振られた $ M $ 個のボールが入っています。 以下の操作を、$ N $ 個のマスがすべて黒く塗られるまで繰り返します。 1. 箱から $ 1 $ つボールを取り出す。取り出し方は完全ランダムであり、各ボールは等確率で選ばれる。 2. 取り出したボールの番号を $ x $ として、マス $ L_x,\ L_x+1,\ \ldots,\ R_x $ を黒く塗る。 3. 取り出したボールを箱に戻す。 操作回数の期待値を $ \text{mod\ }\ 998244353 $ で求めてください（注記参照）。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \hspace{0.5cm}\vdots $ $ L_M $ $ R_M $

求めた期待値を $ \text{mod\ }\ 998244353 $ で出力せよ。

3 3
1 1
1 2
2 3

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

### 注記 求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $ 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 $ - 入力はすべて整数 ### Sample Explanation 1 求める期待値は $ \frac{7}{2} $ です。 $ 499122180\ \times\ 2\ \equiv\ 7\pmod{998244353} $ なので、$ 499122180 $ を出力します。