题目描述

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

题目大意

有一个随机数生成器，生成 $[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$。

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