← 返回题目列表

Codeforces · 1473/G

G. 瓷砖

中文机器翻译题面 查看原题

考虑一条由多行组成的道路。每行被分成若干个矩形瓷砖,同一行中的所有瓷砖都是相等的。第一行恰好包含一个矩形图块。看下图,它显示了瓷砖的排列方式。

道路建设如下:

- 第一行由 $$$1$$$ 组成;
- 然后是 $$$a_1$$$ 行;这些行中的每一行都包含比前一行大的 $$$1$$$ 平铺;
- 然后是 $$$b_1$$$ 行;这些行中的每一行都比前一行少包含 $$$1$$$ 块;
- 然后是 $$$a_2$$$ 行;这些行中的每一行都包含比前一行大的 $$$1$$$ 平铺;
- 然后是 $$$b_2$$$ 行;这些行中的每一行都比前一行少包含 $$$1$$$ 块;
- ...
- 然后是 $$$a_n$$$ 行;这些行中的每一行都包含比前一行大的 $$$1$$$ 平铺;
- 然后是 $$$b_n$$$ 行;这些行中的每一行都比前一行少包含 $$$1$$$ 块。

道路示例 $$$n = 2$$$、$$$a_1 = 4$$$、$$$b_1 = 2$$$、$$$a_2 = 2$$$、$$$b_2 = 3$$$。行从左到右排列。

您从第一行中唯一的图块开始,并想要到达最后一行(其中的任何图块)。从当前图块,您可以移动到下一行中与当前图块接触的任何图块。

计算从第一行到最后一行的不同路径的数量。由于它可能很大,因此打印它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$)。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^5$$$; $$$|a_i - b_i| \le 5$$$)。

对输入的附加约束:$$$a_i$$$ 和 $$$b_i$$$ 的序列永远不会导致具有非正数图块的行。

输出

打印一个整数 — 从第一行到最后一行的路径数,以 $$$998244353$$$ 为模。

示例

输入 #1

2
4 2
2 3

输出 #1

850

输入 #2

3
4 1
2 3
3 1

输出 #2

10150

输入 #3

8
328 323
867 868
715 718
721 722
439 435
868 870
834 834
797 796

输出 #3

759099319