题目描述

给定 $n$ 个区间 $p_i, q_i$。

求$\sum\limits_{s_1={p_1}}^{q_1}\sum\limits_{s_2={p_2}}^{q_2}\sum\limits_{s_3={p_3}}^{q_3} \cdots\sum\limits_{s_n={p_n}}^{q_n}\max\limits_{i=1}^ns_i$ 对 $998244353$ 取余的值。

输入格式

第 $1$ 行，一个整数 $n$，表示区间数量。

第 $2$ 至 $(n+1)$ 行，每行两个整数 $p_i,q_i$。

输出格式

一个整数，表示答案。你需要将答案取余 $998244353$ 后输出。

2
1 4
2 3

24

见文件附件的 sum2.in

见文件附件的 sum2.ans

提示

样例解释

取 $s = \{1, 2\}, \max\limits_{i=1}^ns_i=2$。

取 $s = \{2, 2\}, \max\limits_{i=1}^ns_i = 2$。

取 $s = \{3, 2\}, \max\limits_{i=1}^ns_i = 3$。

取 $s = \{4, 2\}, \max\limits_{i=1}^ns_i= 4$。

取 $s = \{1, 3\}, \max\limits_{i=1}^ns_i=3$。

取 $s = \{2, 3\}, \max\limits_{i=1}^ns_i = 3$。

取 $s = \{3, 3\}, \max\limits_{i=1}^ns_i = 3$。

取 $s = \{4, 3\}, \max\limits_{i=1}^ns_i= 4$。

$2+2+3+4+3+3+3+4 = 24$。

数据范围

对于 $30\%$ 的数据，保证 $n \leq 8$，$p_i, q_i \leq 10$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 5 \times 10^3$，$1 \leq p_i \leq q_i \leq 5 \times 10^3$。有区间可能相同。