P6555 Forget You

"By the way, who are you?" "So you are doing this..." "That makes sense..." "After all, you took away thousands, tens of thousands of abilities," "the burden they put on the brain is really huge," "so it is already very good that you can still talk to people normally." "..." "As for me," "I am your lover."

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$.

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 the remainder of the sum of the research values of all gene samples divided by $998244353$.

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