普及模拟赛 15 - E

时间限制：3000ms

空间限制：512MB

问题描述

给出长度为 $n$ 的正整数序列 $l_i,r_i$​。

请问有多少个长度为 $n$ 的单调不增序列 $a$，满足 $l_i \leq a_i \leq r_i$。

答案对 $998244353$ 取模。

输入格式

输入第一行，包含 $1$ 个正整数 $n$。

之后 $n$ 行，每行给出两个正整数 $l_i,r_i$。

输出格式

对于每组数据，输出一行，表示答案。

样例输入1

3
1 2
1 2
1 2

样例输出1

4

样例解释1

合法序列有 $(2,2,2),(2,2,1),(2,1,1),(1,1,1)$。

样例输入2

10
24 73
57 82
10 99
27 777
11 289
22 73
57 81
10 900
27 1000
11 1145

样例输出2

839522421

数据范围

对于 $30\%$ 的数据，$\sum_{i=1}^n r_i - l_i \leq 10^6$。

对于另外 $30\%$ 的数据，所有 $l_i$ 相等，所有 $r_i$ 相等​。

对于 $80\%$ 的数据，$1 \leq n \leq 100$。

对于所有测评数据，$1 \leq n \leq 500,1 \leq l_i \leq r_i \leq 10^8$。