[AGC038E] Gachapon

有一个随机数生成器，生成 $[0,n-1]$ 之间的整数，其中生成 $i$ 的概率为 $\frac{A_i}{S}$，其中，$S=\sum A_i$。 这个随机数生成器不断生成随机数，当 $\forall i\in[0,n-1]$，$i$ 至少出现了 $B_i$ 次时，停止生成，否则继续生成。 求期望生成随机数的次数，输出答案对 $998244353$ 取模的结果。 $A_i,B_i\geq 1$，$\sum A_i,\sum B_i,n\leq 400$。

[problemUrl]: https://atcoder.jp/contests/agc038/tasks/agc038_e すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、$ 0 $ 以上 $ N-1 $ 以下の整数を生成します。 それぞれの整数を生成する確率は、整数列 $ A_0,A_1,\cdots,A_{N-1} $ によって表され、 整数 $ i $ ($ 0\ \leq\ i\ \leq\ N-1 $) が生成される確率は $ A_i\ /\ S $ です。 ただしここで $ S\ =\ \sum_{i=0}^{N-1}\ A_i $ とします。 また、乱数生成は毎回独立に行われます。 すぬけくんはこれから、次の条件が満たされるまで、乱数生成を繰り返します。 - すべての $ i $ ($ 0\ \leq\ i\ \leq\ N-1 $) について、今までに乱数生成器が $ i $ を生成した回数が $ B_i $ 回以上である。 すぬけくんが操作を行う回数の期待値を求めてください。 ただし、期待値は mod $ 998244353 $ で出力してください。 より正確には、期待値が既約分数 $ P/Q $ で表されるとき、 $ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ <\ 998244353 $ を満たす整数 $ R $ が一意に定まるので、その $ R $ を出力してください。 なお、操作の回数の期待値が有理数として存在し、 さらに mod $ 998244353 $ での整数表現が定義できることが問題の制約から証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_0 $ $ B_0 $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $

すぬけくんが操作を行う回数の期待値を mod $ 998244353 $ で出力せよ。

2
1 1
1 1

3

3
1 3
2 2
3 1

971485877

15
29 3
78 69
19 15
82 14
9 120
14 51
3 7
6 14
28 4
13 12
1 5
32 30
49 24
35 23
2 9

371626143

### 制約 - $ 1\ \leq\ N\ \leq\ 400 $ - $ 1\ \leq\ A_i $ - $ \sum_{i=0}^{N-1}\ A_i\ \leq\ 400 $ - $ 1\ \leq\ B_i $ - $ \sum_{i=0}^{N-1}\ B_i\ \leq\ 400 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 すぬけくんが操作を行う回数の期待値は $ 3 $ です。 ### Sample Explanation 2 すぬけくんが操作を行う回数の期待値は $ 132929/7200 $ です。