El jefe de la empresa Radek y sus amigos, Radek, ha intentado inundar todas las estanterías con documentos en la empresa competidora Mati y compañía. Para llevar a cabo un sabotaje perfecto, le pidió a su amigo, el fontanero Janusz, que instalara pequeños grifos de agua sobre cada una de las estanterías.

Las estanterías en la empresa Mati y compañía pueden representarse, para simplificar, mediante segmentos en un plano. Cada estantería es un segmento entre un par de puntos $(l_i, h_i)$ y $(r_i, h_i)$. Los grifos instalados por el fontanero son puntos con coordenadas $(\frac{l_i+r_i}{2}, h_i + 0.5)$. El suelo de esta habitación está representado por el eje $OX$.

En el momento en que se abre el grifo sobre la $i$-ésima estantería, dicha estantería se inunda. Como consecuencia natural, el agua comienza a gotear verticalmente hacia abajo desde los extremos de las estanterías, inundando potencialmente las estanterías inferiores o goteando hasta el suelo con un sistema natural de drenaje.

Visualización del agua fluyendo tras abrir un grifo en el segundo caso de prueba.

Radek considerará los grifos en un orden determinado. En el momento en que considera el $i$-ésimo grifo, lo abre si y solo si la $i$-ésima estantería aún no está inundada.

Radek aún no ha establecido el orden en el que considerará los grifos. Elegirá al azar uno de los $n!$ órdenes posibles, cada uno con la misma probabilidad. Radek ahora quiere saber cuántos grifos tendrá que abrir en promedio.

Tu tarea es responder a la pregunta de Radek y proporcionar la respuesta módulo $10^9 + 7$. Formalmente, sea el resultado igual a $\frac{p}{q}$, donde $q \neq 0$ y $\text{mcd}(p, q) = 1$. Entonces, debes imprimir el número $p \cdot q^{-1} \pmod{10^9 + 7}$, donde $q^{-1}$ es el único número del conjunto $1, 2, \dots, 10^9 + 6$ tal que $q \cdot q^{-1} \equiv 1 \pmod{10^9 + 7}$.

Se puede demostrar que para todos los casos de prueba que cumplen las condiciones del problema, el resultado es un número racional cuyo denominador en forma irreducible no es divisible por $10^9 + 7$.

Entrada

La primera línea de la entrada contiene un número natural $n$ ($1 \le n \le 500\,000$), que especifica el número de estanterías en la empresa de Mati.

En las siguientes $n$ líneas se encuentra la descripción de las estanterías. En la $i$-ésima de estas líneas hay dos números naturales $l_i, r_i$ ($1 \le l_i < r_i \le 2 \cdot n$), descritos en el enunciado del problema. Para simplificar, asumimos que $h_i = i$.

Puedes asumir que todos los números $l_i, r_i$ son distintos entre sí; los números $l_i, r_i$ forman una permutación de los números del $1$ al $2 \cdot n$.

Salida

En la única línea de la salida estándar debe aparecer un número igual al número promedio de grifos que Radek tendrá que abrir, módulo $10^9 + 7$.

Ejemplos

Entrada 1

3
4 6
1 3
2 5

Salida 1

2

Entrada 2

5
2 9
3 4
1 8
6 10
5 7

Salida 2

233333338

Nota

Explicación del ejemplo: Consideremos todos los órdenes posibles en los que Radek analizará los grifos en el primer caso de prueba:

• Para el orden 1, 2, 3, abrirá los 3 grifos.
• Para el orden 1, 3, 2, abrirá el primer y el tercer grifo. Tras abrir el tercer grifo, el agua inundará también la segunda estantería, por lo que no necesita abrir el segundo grifo.
• Para el orden 2, 1, 3, abrirá los 3 grifos.
• Para el orden 2, 3, 1, abrirá el segundo y el tercer grifo. Tras abrir el tercer grifo, el agua inundará la primera estantería, por lo que no hay necesidad de abrir el primer grifo.
• Para los órdenes 3, 1, 2 y 3, 2, 1, solo abrirá el tercer grifo. Tras abrirlo, todas las estanterías quedarán inundadas, por lo que no hay necesidad de abrir otros grifos.

Por lo tanto, Radek debe abrir en promedio $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$ grifos.

En el segundo caso de prueba, Radek debe abrir en promedio $\frac{91}{30}$ grifos. Dado que $30^{-1} \equiv 233333335 \pmod{10^9 + 7}$, tenemos $91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9 + 7}$.