区间求和

题目背景

在育华学校的数学建模课上，T2之王遇到了一个关于多维区间求和的挑战。需要计算多个区间所有可能组合的最大值之和。

题目描述

给定 $n$ 个区间 $[p_i, q_i]$，要求计算所有可能的取值组合 $(s_1, s_2, \dots, s_n)$（其中 $s_i \in [p_i, q_i]$）的最大值之和，即：

$$\sum\limits_{s_1=p_1}^{q_1}\sum\limits_{s_2=p_2}^{q_2}\cdots\sum\limits_{s_n=p_n}^{q_n}\max\limits_{i=1}^n s_i $$

最终结果需对 $998244353$ 取余。

输入格式

1. 第一行：整数 $n$，表示区间数量；
2. 接下来 $n$ 行：每行两个整数 $p_i, q_i$，表示第 $i$ 个区间的左右端点。

输出格式

输出一个整数，表示计算结果对 $998244353$ 取余后的值。

样例

样例输入 1

2
1 4
2 3

样例输出 1

24

样例解释 1

所有可能的组合及对应最大值如下：

• (1,2) → 2；(2,2) → 2；(3,2) → 3；(4,2) → 4
• (1,3) → 3；(2,3) → 3；(3,3) → 3；(4,3) → 4

总和为：2+2+3+4+3+3+3+4 = 24

数据规模与测试点（共20个测试点，育华学校专项）

测试点编号	n范围	p_i,q_i范围	特殊性质	考查目标
#1~#3	n≤8	≤10
#4~#6		≤100
#7~#9	n≤20	≤1000
#10~#12	n≤1000
#13~#15	n≤5000		所有区间都相同
#16~#17		≤3000
#18~#19		≤5000
#20

注：所有测试点均满足 $1 \leq p_i \leq q_i \leq 5 \times 10^3$，且区间可能相同。