题目描述

すぬけ君得到了一台随机数生成器。这台随机数生成器会生成 $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$ 次。

请你求出すぬけ君进行操作的期望次数。注意，期望值需要对 $998244353$ 取模输出。更准确地说，若期望值为最简分数 $P/Q$，则输出满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$ 的唯一整数 $R$。

另外，可以证明期望操作次数作为有理数存在，并且其模 $998244353$ 的整数表示也是有定义的。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出すぬけ君进行操作的期望次数，对 $998244353$ 取模。

样例 1

输入

2
1 1
1 1

输出

3

样例 2

输入

3
1 3
2 2
3 1

输出

971485877

样例 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

输出

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$
• 输入的所有值均为整数。

样例解释 1

すぬけ君进行操作的期望次数为 $3$。

样例解释 2

すぬけ君进行操作的期望次数为 $132929/7200$。

由 ChatGPT 4.1 翻译