Tiles
Contest: Educational Codeforces Round 102 (Rated for Div. 2)
Difficulty rating: 2800
Tags: combinatorics, dp, fft, math

Consider a road consisting of several rows. Each row is divided into several rectangular tiles, and all tiles in the same row are equal. The first row contains exactly one rectangular tile. Look at the picture below which shows how the tiles are arranged.

The road is constructed as follows:

- the first row consists of $$$1$$$ tile;
- then $$$a_1$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;
- then $$$b_1$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row;
- then $$$a_2$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;
- then $$$b_2$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row;
- ...
- then $$$a_n$$$ rows follow; each of these rows contains $$$1$$$ tile greater than the previous row;
- then $$$b_n$$$ rows follow; each of these rows contains $$$1$$$ tile less than the previous row.

An example of the road with $$$n = 2$$$, $$$a_1 = 4$$$, $$$b_1 = 2$$$, $$$a_2 = 2$$$, $$$b_2 = 3$$$. Rows are arranged from left to right.

You start from the only tile in the first row and want to reach the last row (any tile of it). From your current tile, you can move to any tile in the next row which touches your current tile.

Calculate the number of different paths from the first row to the last row. Since it can be large, print it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$).

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^5$$$; $$$|a_i - b_i| \le 5$$$).

Additional constraint on the input: the sequence of $$$a_i$$$ and $$$b_i$$$ never results in a row with non-positive number of tiles.

Output format:
Print one integer — the number of paths from the first row to the last row, taken modulo $$$998244353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
2
4 2
2 3

Example output:
850

Example input:
3
4 1
2 3
3 1

Example output:
10150

Editorial:
The group of the rows where the number of rectangular tiles increases $$$a$$$ times and then decreases $$$b$$$ times can be represented as a rectangular table, with $$$a+b+1$$$ diagonals, where the size of the first diagonal is equal to the number of rectangular tiles before the operations are applied (let their number be $$$m$$$), and the size of the last diagonal is $$$m+a-b$$$.
In such a rectangular table, one can move from the cell $$$(i, j)$$$ to the cells $$$(i+1, j)$$$ and $$$(i, j+1)$$$ (if they exist), which lie on the next diagonal (next row in terms of the original problem). It's a well-known fact that the number of different paths from one cell to another is some binomial coefficient.
Let's define $$$ans_{i,j}$$$ as the number of paths from the $$$1$$$-st row to the $$$j$$$-th tile in the ($$$\sum\limits_{k=1}^{i} (a_i+b_i)$$$)-th row (i.e. row after the $$$i$$$-th group of operations).
Now we want to find the values of $$$ans_{i}$$$ using the values of $$$ans_{i-1}$$$ (let its size be $$$m$$$). Using the fact described in the first paragraphs we know that $$$ans_{i, j}$$$ depends on $$$ans_{i-1, k}$$$ with some binomial coefficient. In fact $$$ans_{i, j} = \sum\limits_{k=1}^{m} \binom{a_i+b_i}{b_i-k+j} ans_{i-1,k}$$$ for $$$1 \le j \le m + a_i - b_i$$$. But this solution is too slow. To speed up this solution we have to notice that the given formula is a convolution of $$$ans_{i-1}$$$ and some binomial coefficients. So we can use NTT to multiply them in $$$O(n\log n)$$$ instead of $$$O(n^2)$$$ time.