Note

Problem Statement

You are given positive integers $L_i, M_i \ (i = 1, \dots, K)$ as input, where $L_1 < L_2 < \dots < L_K$. A Young diagram of type $(L, M)$ is the figure obtained by, for $i = 1, \dots, K$ in order from the bottom, stacking $M_i$ rows, each consisting of $L_i$ squares of side length 1 placed side by side horizontally. For example, if $K = 2, (L_1, M_1) = (2, 2), (L_2, M_2) = (3, 1)$, the figure has the shape
$\Box \Box \Box \\ \Box \Box \\ \Box \Box$
.
Let $N$ be the number of squares in this Young diagram, and consider assigning the numbers from $1$ to $N$ to the squares, one number per square. An assignment is called a "good assignment" if, in each row, the numbers increase from left to right, and, among rows having the same width, the numbers assigned to the leftmost squares of the rows increase from bottom to top.
For example, for the Young diagram above,
$2 \ 4 \ 5 \\ 3 \ 6 \\ 1 \ 7$
is a good assignment.
Find the number of good assignments for the Young diagram constructed from the given $L_i, M_i$, modulo $998244353$.

Input

$K$
$L_1 \ M_1$
$\vdots$
$L_K \ M_K$

$1 \leq K \leq 10^3,$
$1 \leq L_1 < L_2 < \dots < L_K,$
$1 \leq M_i \ (i = 1, \dots, K),$
$L_1 M_1 + L_2 M_2 + \dots + L_K M_K \leq 10^8.$

Output

Sample

1
2 2

3

1
5 2

126

3
1 2
3 4
5 6

144824767