Description

To help おとさか ゆう recover his memories, ともり なお found PZY.

After research, PZY found that abilities are mainly determined by the ability genes in the body. He labeled a total of $m$ ability genes as $1$ to $m$, and then divided them in order into $n$ sets. The $i$-th set contains $a_i$ ability genes with indices from $(\sum\limits_{j=1}^{i-1} a_j)+1$ to $\sum\limits_{j=1}^{i} a_j$.

After many experiments, PZY found that the ordering of genes can be simplified into a sequence. As required, he defines a sequence to be a gene sample if and only if the sequence consists only of numbers from $1$ to $m$. For numbers that belong to the $i$-th set, they must be non-strictly increasing within the sequence, and each number appears in the sequence no more than $b_i$ times.

In particular, the research value of a gene sample is the sum of all numbers that make up the gene sample. Note that repeated numbers should also be counted repeatedly.

To help おotasaка ゆう recover his memories, PZY wants to know the sum of the research values of all gene samples.

Since the answer is very large, he only wants the remainder after dividing the answer by $998244353$.

Input Format

The first line contains a positive integer $n$.

Lines $2$ to $n+1$ each contain two positive integers $a_i, b_i$, with the meaning as described in the statement.

Output Format

Output the remainder of the sum of the research values of all gene samples divided by $998244353$.

2
2 2
1 2

300

3
2 2
3 6
2 4

661677771

Hint

Explanation of Sample 1:

The two sets are $\{ 1 , 2 \}$ and $\{ 3 \}$.

For gene samples of length $1$, we have: $1, 2, 3$.
The total value is $1+2+3=6$.

For gene samples of length $2$, we have: $11, 12, 13, 22, 23, 31, 32, 33$.
The total value is $1+1+1+2+1+3+2+2+2+3+3+1+3+2+3+3=33$.
The sequence $21$ does not satisfy the requirement that numbers in set $1$ are non-strictly increasing in the sequence.

For gene samples of length $3$, we have: $113, 123, 131, 132, 133, 223, 232, 233, 311, 312, 313, 322, 323, 331, 332$.
The total value is $99$.
The sequences $111, 112, 122, 222, 333$ exceed the occurrence limit.

For gene samples of length $4$, the total value is $162$.

So the total value is $6+33+99+162=300$.

Let $k=\sum\limits_i b_i$.

For $10\%$ of the testdata, $1\le n\le 3, 1\le k\le 10, 1\le a_i\le 5$.
For another $20\%$ of the testdata, $n=1, 1\le k\le 10^5, 1 \le a_i \le 10^6$.
For another $30\%$ of the testdata, $n=2, 2\le k\le 10^5, 1 \le a_i \le 10^6$.
For $100\%$ of the testdata, $1\le n \le k\le 10^5, 1 \le a_i \le 10^6$.

Translated by ChatGPT 5