E - Gachapon Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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 で出力せよ。

入力例 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

Score : 1600 points

Problem Statement

Snuke found a random number generator. It generates an integer between 0 and N-1 (inclusive). An integer sequence A_0, A_1, \cdots, A_{N-1} represents the probability that each of these integers is generated. The integer i (0 \leq i \leq N-1) is generated with probability A_i / S, where S = \sum_{i=0}^{N-1} A_i. The process of generating an integer is done independently each time the generator is executed.

Now, Snuke will repeatedly generate an integer with this generator until the following condition is satisfied:

  • For every i (0 \leq i \leq N-1), the integer i has been generated at least B_i times so far.

Find the expected number of times Snuke will generate an integer, and print it modulo 998244353. More formally, represent the expected number of generations as an irreducible fraction P/Q. Then, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353, so print this R.

From the constraints of this problem, we can prove that the expected number of generations is a finite rational number, and its integer representation modulo 998244353 can be defined.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 B_0
A_1 B_1
\vdots
A_{N-1} B_{N-1}

Output

Print the expected number of times Snuke will generate an integer, modulo 998244353.

Sample Input 1

2
1 1
1 1

Sample Output 1

3

The expected number of times Snuke will generate an integer is 3.

Sample Input 2

3
1 3
2 2
3 1

Sample Output 2

971485877

The expected number of times Snuke will generate an integer is 132929/7200.

Sample Input 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

Sample Output 3

371626143