There is a sequence $a_1, a_2, \dots, a_n$ of length $n$, where each $a_i$ is a real number independently and uniformly generated from the interval $[l_i, r_i]$.

If $1 \le i < j \le n$ and $a_i > a_j$, we call $(i, j)$ an inversion. You need to find the expected number of inversions in this sequence. For simplicity, you only need to output the expected value modulo $998244353$.

Input

The first line contains a single positive integer $n$.

The next $n$ lines each contain two non-negative integers $l_i, r_i$.

Output

Output the expected number of inversions modulo $998244353$.

Examples

Input 1

3
2 3
4 5
1 6

Output 1

1

Subtasks

For all data, $0 \le l_i < r_i \le 10^8$.

• Subtask 1 (20pts): $n \le 3$, $r_i \le 5$.
• Subtask 2 (20pts): $n \le 10$.
• Subtask 3 (20pts): $n \le 1000$.
• Subtask 4 (20pts): $n \le 10^5$, $l_i = 0$.
• Subtask 5 (20pts): $n \le 10^5$.