The boss of the company "Radek and friends," Radek, has attempted to flood all the shelves with documents at the competing company "Mati and Co." To perform the perfect sabotage, he asked his friend, the plumber Janusz, to install small water taps above each of the shelves.

The shelves at "Mati and Co." can be simplified and represented as line segments on a plane. Each shelf is a segment between a pair of points $(l_i, h_i)$ and $(r_i, h_i)$. The taps installed by the plumber are points with coordinates $(\frac{l_i+r_i}{2}, h_i + 0.5)$. The floor in this room is represented by the $OX$ axis.

When the tap above the $i$-th shelf is turned on, that shelf becomes flooded. As a natural consequence, water begins to drip vertically downwards from the ends of the shelves and potentially floods subsequent shelves or drips onto the floor with a natural drainage system.

Visualization of water flowing after turning on one tap in the second example test.

Radek will consider the taps in a certain fixed order. When he considers the $i$-th tap, he turns it on if and only if the $i$-th shelf is not yet flooded.

Radek has not yet determined the order in which he will consider the taps. He will choose one of the $n!$ permutations at random, with each being equally likely. Radek would now like to know how many taps he will have to turn on, on average.

Your task is to answer Radek's question and provide the answer modulo $10^9 + 7$. Formally, let the result be $\frac{p}{q}$, where $q \neq 0$ and $\gcd(p, q) = 1$. Then you should output the number $p \cdot q^{-1} \pmod{10^9 + 7}$, where $q^{-1}$ is the unique number from the set $\{1, 2, \dots, 10^9 + 6\}$ such that $q \cdot q^{-1} \equiv 1 \pmod{10^9 + 7}$.

It can be proven that for all test cases satisfying the problem conditions, the result is a rational number whose denominator in irreducible form is not divisible by $10^9 + 7$.

Input

The first line of input contains a single natural number $n$ ($1 \le n \le 500\,000$), representing the number of shelves at Mati's company.

The next $n$ lines contain the description of the shelves. The $i$-th of these lines contains two natural numbers $l_i, r_i$ ($1 \le l_i < r_i \le 2 \cdot n$), as described in the problem statement. For simplicity, we assume $h_i = i$.

You may assume that all numbers $l_i, r_i$ are pairwise distinct — the numbers $l_i, r_i$ form a permutation of numbers from $1$ to $2 \cdot n$.

Output

The only line of standard output should contain a single number equal to the average number of taps that Radek will have to turn on, modulo $10^9 + 7$.

Examples

Input 1

3
4 6
1 3
2 5

Output 1

2

Input 2

5
2 9
3 4
1 8
6 10
5 7

Output 2

233333338

Note

Explanation of the example: Let us consider all possible orders in which Radek will analyze the taps in the first example test:

• For the order 1, 2, 3, he will turn on all 3 taps.
• For the order 1, 3, 2, he will turn on the first and third tap. After turning on the third tap, water will also flood the second shelf, so he does not need to turn on the second tap.
• For the order 2, 1, 3, he will turn on all 3 taps.
• For the order 2, 3, 1, he will turn on the second and third tap. After turning on the third tap, water will flood the first shelf, so there is no need to turn on the first tap.
• For the orders 3, 1, 2 and 3, 2, 1, he will only turn on the third tap. After turning it on, all shelves will be flooded, so there is no need to turn on other taps.

On average, Radek must therefore turn on $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$ taps.

In the second example test, Radek must turn on $\frac{91}{30}$ taps on average. We have $30^{-1} \equiv 233333335 \pmod{10^9 + 7}$, so we have $91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9 + 7}$.