考虑一条由多行组成的道路。每行被分成若干个矩形瓷砖,同一行中的所有瓷砖都是相等的。第一行恰好包含一个矩形图块。看下图,它显示了瓷砖的排列方式。
道路建设如下:
- 第一行由 $$$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