配点 : $1600$ 点

問題文

すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、$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$ での整数表現が定義できることが問題の制約から証明できます。

制約

• $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$
• 入力される値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$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$ です。

3
1 3
2 2
3 1

971485877

すぬけくんが操作を行う回数の期待値は $132929/7200$ です。

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