Description

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

Input Format

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 Format

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

2
1 1
1 1

4

2
1 2
1 2

3

5
1 3
2 4
5 5
2 5
1 5

776412281

Hint

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.

Translated by ChatGPT 4.1