Problem Description

Given $n$ intervals $p_i, q_i$.

Compute $\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$ modulo $998244353$.

Input Format

Line $1$ contains an integer $n$, representing the number of intervals.

Lines $2$ to $(n+1)$ each contain two integers $p_i, q_i$.

Output Format

Output one integer, representing the answer. You need to output the answer modulo $998244353$.

2
1 4
2 3

24

见文件附件的 sum2.in

见文件附件的 sum2.ans

Hint

Sample Explanation

Take $s = \{1, 2\}$, $\max\limits_{i=1}^ns_i = 2$.

Take $s = \{2, 2\}$, $\max\limits_{i=1}^ns_i = 2$.

Take $s = \{3, 2\}$, $\max\limits_{i=1}^ns_i = 3$.

Take $s = \{4, 2\}$, $\max\limits_{i=1}^ns_i = 4$.

Take $s = \{1, 3\}$, $\max\limits_{i=1}^ns_i = 3$.

Take $s = \{2, 3\}$, $\max\limits_{i=1}^ns_i = 3$.

Take $s = \{3, 3\}$, $\max\limits_{i=1}^ns_i = 3$.

Take $s = \{4, 3\}$, $\max\limits_{i=1}^ns_i = 4$.

$2 + 2 + 3 + 4 + 3 + 3 + 3 + 4 = 24$.

Constraints

For $30\%$ of the testdata, it is guaranteed that $n \leq 8$, and $p_i, q_i \leq 10$.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 5 \times 10^3$, $1 \leq p_i \leq q_i \leq 5 \times 10^3$. Some intervals may be identical.

Translated by ChatGPT 5