Tiles

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

一条道路由许多行矩形瓷砖组成，同一行中的瓷砖大小相同。第一行只有一块瓷砖。

随后依次进行 $n$ 组变化：先有 $a_i$ 行，每一行比前一行多一块瓷砖；再有 $b_i$ 行，每一行比前一行少一块瓷砖。

你从第一行唯一的瓷砖出发。每一步可以走到下一行中与当前瓷砖相接触的任意瓷砖。求到达最后一行任意瓷砖的不同路径数，对 $998244353$ 取模。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $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

数据范围

$1\le n\le1000$，$1\le a_i,b_i\le10^5$，$\lvert a_i-b_i\rvert\le5$。