题目描述

Snuke发现了一个随机数生成器。它生成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$。每次执行生成器时，生成一个整数的过程是独立进行的。

现在，Snuke将重复使用该生成器生成整数，直到满足以下条件为止：

• 对于每个$i$（$0 \leq i \leq N-1$），到目前为止，整数$i$至少已生成了$B_i$次。

找出Snuke生成一个整数的期望次数，并将其对$998244353$取模后打印。更正式地说，将生成次数的期望表示为不可约分数$P/Q$。然后，存在一个唯一的整数$R$，满足$R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$，因此打印这个$R$。

从该问题的约束条件中，我们可以证明生成次数的期望是一个有限的有理数，并且可以定义其对$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}$

输出

将Snuke生成一个整数的期望次数对$998244353$取模后打印。

示例输入 1

2
1 1
1 1

示例输出 1

3

Snuke生成一个整数的期望次数为$3$。

示例输入 2

3
1 3
2 2
3 1

示例输出 2

971485877

Snuke生成一个整数的期望次数是$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