P14008 Sequence Game

**Please note the time limit for this problem.** For a sequence $a$, we define its weight as the sum of the squares of the lengths of all maximal color segments. A color segment is defined as an interval $a_l, a_{l+1}, \dots, a_r$ where all elements are equal. A maximal color segment is a color segment that cannot be contained within any longer color segment. Given a sequence $a$ of length $n$, where each $a_i$ is an integer chosen uniformly at random from the interval $[l_i, r_i]$, compute the expected value of the weight over all possible sequences $a$, modulo $998244353$.

The first line contains a single integer $n$, representing the length of the sequence. The next $n$ lines each contain two integers $l_i$ and $r_i$, indicating the random range for $a_i$.

Output a single integer, representing the expected weight over all possible sequences $a$.

### Sample Explanation #### Sample Explanation #1 Obviously, in this case $a = \{1, 1\}$, so the expected weight is $2^2 = 4$. #### Sample Explanation #2 In this case, the four possible sequences are $a = \{1, 1\}, a = \{1, 2\}, a = \{2, 1\}, a = \{2, 2\}$. For $\{1, 1\}$ and $\{2, 2\}$, the weight is $2^2 = 4$, and for $\{1, 2\}$ and $\{2, 1\}$, the weight is $1^2 + 1^2 = 2$. Therefore, the expected weight is $\frac{4+4+2+2}{4} = 3$. ### Data Range **This problem uses bundled testing.** | Subtask | Score | $n\le$ | $r_i\le$ | Special Properties | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | 1 | $10$ | $5$ | $5$ | None | | 2 | $10$ | $2000$ | $2000$ | None | | 3 | $20$ | $10^5$ | $10^5$ | None | | 4 | $20$ | $10^5$ | $9\times 10^8$ | None | | 5 | $10$ | $10^6$ | $9\times 10^8$ | Data is random | | 6 | $30$ | $2\times 10^6$ | $9\times 10^8$ | None | Translated by ChatGPT 4.1