P8894 "UOI-R1" Summation

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$.

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 one integer, representing the answer. You need to output the answer modulo $998244353$.

### 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