기대 아름다움

시간 제한1초메모리 제한2048 MB

요약

각 A_i는 L_i부터 R_i까지의 정수 중 균등하게 뽑힌 값입니다. 인접한 같은 값 중 하나를 지우고 그 값을 점수에 더할 때, 얻을 수 있는 점수 제곱의 최댓값의 기댓값을 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 확률, 수학
정답자: 아직 제출이 없습니다

문제

Morgan 로봇은 1번부터 $N$ 번까지 인덱스가 붙은 길이 $N$ 의 배열 $A$ 를 가지고 있다. 각 원소의 값은 무작위로 정해진다. $A_i$ 는 $L_i$ 이상 $R_i$ 이하의 임의의 정수이며, 각 값이 선택될 확률은 같다.

Morgan은 $A$ 의 아름다움을 다음과 같이 정의한다. 먼저 값이 $0$ 인 변수 score가 있다. 배열 $a$ 에 대한 연산은 다음과 같다.

$1 \le i < |a|$ 이고 $a_i = a_{i+1}$ 인 인덱스 $i$ 를 고른다. 그런 $i$ 가 없으면 이 연산은 할 수 없다.
$a_i$ 의 값을 score에 더하고, $a_i$ 를 배열에서 제거한다.
남은 원소들은 순서를 유지한 채 이어 붙는다.

$A$ 의 아름다움은 $A$ 에 대해 연산을 0번 이상 수행한 뒤 Morgan이 얻을 수 있는 score $^2$ 의 최댓값이다.

배열이 무작위로 만들어지므로 Morgan은 $A$ 의 아름다움의 기댓값이 궁금하다. Morgan의 알고리즘은 너무 느려서, 기댓값 계산을 도와달라고 요청했다.

입력

첫 줄에 정수 $N$ ( $1 \le N \le 200000$ )이 주어진다. 이후 $N$ 개의 줄에 각각 두 정수 $L_i$ 와 $R_i$ ( $1 \le L_i \le R_i \le 10^8$ )가 주어진다.

출력

$M = 998244353$ 으로 둔다. 기댓값은 기약분수 $p/q$ 로 나타낼 수 있으며, $q \not\equiv 0 \pmod M$ 이다. $0 \le x < M$ 이고 $x \cdot q \equiv p \pmod M$ 을 만족하는 정수 $x$ 를 한 줄에 출력한다.

예제3

예제 1
입력
```
3
1 2
2 3
1 3
```
예상 출력
```
831870298
```
예제 2
입력
```
4
1 1
1 1
2 2
2 2
```
예상 출력
```
9
```
예제 3
입력
```
3
1 2
3 4
5 6
```
예상 출력
```
0
```