Problem Description

Translated from PA 2024 Round 5 Kraniki

Radek, the head of Radek and Friends company, is trying to flood all the shelves of the competitor Mati and Company company. To execute the perfect sabotage, he has his friend, plumber Janusz, install small faucets on each shelf.

For simplicity, the shelves in Mati and Company can be represented by line segments on a plane. Each shelf is a segment between points $(l_i, h_i)$ and $(r_i, h_i)$. The plumber installs the faucets at points $(\frac{l_i+r_i}{2}, h_i + 0.5)$. The floor of the room is represented by the $OX$ axis.

When the faucet above the $i$-th shelf is turned on, that shelf gets flooded. The water then naturally starts dripping vertically down from both ends of the shelf, potentially flooding more shelves or dripping onto the ground.

Visualization of water flow when a faucet is turned on in the second sample case.

Radek will observe the faucets in a certain order. When he sees the $i$-th faucet, he will only turn it on if the $i$-th shelf is not already flooded.

Radek has not decided on the order in which he will observe the faucets. He will choose one of the $n!$ possible orders uniformly at random. Radek wants to know on average how many faucets he will need to turn on.

Your task is to answer Radek's question by outputting the answer modulo $10^9+7$. Formally, let the answer be $\frac{p}{q}$, where $q \neq 0$ and $\gcd(p, q) = 1$. You need to output $p \cdot q^{-1} \pmod{10^9+7}$, where $q^{-1}$ is the unique integer in the set $1, 2, \ldots, 10^9+6$ such that $q \cdot q^{-1} \equiv 1 \pmod{10^9+7}$.

It can be proven that for all valid inputs, the result is measurable, and the denominator in its irreducible form is not divisible by $10^9+7$.

Input Format

The first line contains an integer $n\ (1 \le n \le 500\,000)$, representing the number of shelves in Mati's company.

The next $n$ lines each contain two integers $l_i, r_i\ (1 \le l_i < r_i \le 2 \cdot n)$, representing the $i$-th shelf. For simplicity, we assume $h_i = i$.

You can assume that all $l_i, r_i$ are distinct—the integers $l_i, r_i$ form a permutation of $1$ to $2 \cdot n$.

Output Format

Output a single integer, representing the average number of faucets Radek needs to turn on, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
4 6
1 3
2 5

Sample Output #1

2

Sample Input #2

5
2 9
3 4
1 8
6 10
5 7

Sample Output #2

233333338

Notes/Hints

Sample Explanation 1

Let's consider all possible orders in which Radek observes the faucets in the first sample:

• In order $1, 2, 3$, he will turn on all $3$ faucets.
• In order $1, 3, 2$, he will turn on faucets $1$ and $3$. When he is about to turn on faucet $2$, the shelf is already flooded, so he does not need to turn on faucet $2$.
• In order $2, 1, 3$, he will turn on all $3$ faucets.
• In order $2, 3, 1$, he will turn on faucets $2$ and $3$. When he is about to turn on faucet $1$, the shelf is already flooded, so he does not need to turn on faucet $1$.
• In orders $3, 1, 2$ or $3, 2, 1$, since turning on faucet $3$ floods all shelves, he does not need to turn on the remaining two faucets.

Radek averages $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$ faucets.

Sample Explanation 2

In the second sample, Radek needs to turn on $\frac{91}{30}$ faucets on average. Since $30^{-1} \equiv 233333335 \pmod{10^9+7}$, the output is $91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9+7}$.

见题面 Input 部分

见题面 Output 部分