問題文

すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、$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$ で出力せよ。

入力例 1

2
1 1
1 1

出力例 1

3

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

入力例 2

3
1 3
2 2
3 1

出力例 2

971485877

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

入力例 3

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

出力例 3

371626143