注意

問題文

入力から、正の整数 $L_i, M_i \ (i = 1, \dots, K)$ が与えられる。ただし、$L_1 < L_2 < \dots < L_K$ である。型 $(L, M)$ のヤング図形とは、$i = 1, \dots, K$ に対して、下から順番に辺の長さが 1 の正方形を横に $L_i$ 個並べたものを $M_i$ 段積み上げた結果できる図形のことである。例えば $K = 2, (L_1, M_1) = (2, 2), (L_2, M_2) = (3, 1)$ なら、
$\Box \Box \Box \\ \Box \Box \\ \Box \Box$
という形の図形になる。
このヤング図形の正方形の個数を $N$ とおき、$1$ から $N$ まで順番に各正方形にひとつずつ数字を割り振ることを考える。各段について、左から右にかけて数字が大きくなっており、かつ、同じ横の幅を持つ各段の最左に割り振られた数字が下から上にかけて数字が大きくなっているとき、「よい割り振り」と呼ぶことにする。
例えば、先程のヤング図形について、
$2 \ 4 \ 5 \\ 3 \ 6 \\ 1 \ 7$
はよい割り振りである。
入力で与えられた $L_i, M_i$ から作られるヤング図形へのよい割り振りの個数を $998244353$ で割ったあまりを求めよ。

入力

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

出力

サンプル

1
2 2

3

1
5 2

126

3
1 2
3 4
5 6

144824767