#MX155. 单调不增序列计数

单调不增序列计数

时间限制:3000ms

空间限制:512MB

题目描述

给出长度为 nn 的正整数序列 li,ril_i,r_i​。

请问有多少个长度为 nn 的单调不增序列 aa,满足 li≤ai≤ril_i \leq a_i \leq r_i。

答案对 998244353998244353 取模。

输入格式

输入第一行,包含 11 个正整数 nn。

之后 nn 行,每行给出两个正整数 li,ril_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,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%30\% 的数据,∑i=1nri−li≤106\sum_{i=1}^n r_i - l_i \leq 10^6。

对于另外 30%30\% 的数据,所有 lil_i 相等,所有 rir_i 相等​。

对于 80%80\% 的数据,1≤n≤1001 \leq n \leq 100。

对于所有测评数据,1≤n≤500,1≤li≤ri≤1081 \leq n \leq 500,1 \leq l_i \leq r_i \leq 10^8。