Le patron de l'entreprise Radek et ses amis, Radek, a tenté d'inonder toutes les étagères contenant des documents dans l'entreprise concurrente Mati et Cie. Pour réaliser un sabotage parfait, il a demandé à son ami, le plombier Janusz, d'installer de petits robinets d'eau au-dessus de chacune des étagères.

Les étagères de l'entreprise Mati et Cie peuvent être représentées, pour simplifier, par des segments sur un plan. Chaque étagère est un segment entre une paire de points $(l_i, h_i)$ et $(r_i, h_i)$. Les robinets installés par le plombier sont des points aux coordonnées $(\frac{l_i+r_i}{2}, h_i + 0.5)$. Le sol de cette pièce est représenté par l'axe $OX$.

Au moment où le robinet au-dessus de la $i$-ième étagère est ouvert, cette étagère est inondée. Par conséquent, l'eau commence à s'écouler verticalement vers le bas depuis les extrémités des étagères, inondant potentiellement les étagères situées en dessous ou s'écoulant sur le sol via le système d'évacuation naturel.

Radek examinera les robinets dans un ordre fixe. Lorsqu'il considère le $i$-ième robinet, il ne l'ouvre que si la $i$-ième étagère n'est pas encore inondée.

Radek n'a pas encore déterminé l'ordre dans lequel il examinera les robinets. Il choisira au hasard l'un des $n!$ ordres possibles, chacun avec la même probabilité. Radek souhaite maintenant savoir combien de robinets il devra ouvrir en moyenne.

Votre tâche est de répondre à la question de Radek et de fournir la réponse modulo $10^9 + 7$. Formellement, soit le résultat égal à $\frac{p}{q}$, où $q \neq 0$ et $\text{PGCD}(p, q) = 1$. Vous devez alors afficher le nombre $p \cdot q^{-1} \pmod{10^9 + 7}$, où $q^{-1}$ est l'unique nombre de l'ensemble $\{1, 2, \dots, 10^9 + 6\}$ tel que $q \cdot q^{-1} \equiv 1 \pmod{10^9 + 7}$.

On peut démontrer que pour tous les tests satisfaisant les conditions du problème, le résultat est un nombre rationnel dont le dénominateur sous forme irréductible n'est pas divisible par $10^9 + 7$.

Entrée

La première ligne de l'entrée contient un entier naturel $n$ ($1 \le n \le 500\,000$), représentant le nombre d'étagères dans l'entreprise de Mati.

Les $n$ lignes suivantes contiennent la description des étagères. La $i$-ième ligne contient deux entiers naturels $l_i, r_i$ ($1 \le l_i < r_i \le 2 \cdot n$), décrits dans l'énoncé. Pour simplifier, nous supposons que $h_i = i$.

Vous pouvez supposer que tous les nombres $l_i, r_i$ sont distincts deux à deux — les nombres $l_i, r_i$ forment une permutation des nombres de $1$ à $2 \cdot n$.

Sortie

La seule ligne de la sortie standard doit contenir un nombre égal au nombre moyen de robinets que Radek devra ouvrir, modulo $10^9 + 7$.

Exemples

Entrée 1

3
4 6
1 3
2 5

Sortie 1

2

Entrée 2

5
2 9
3 4
1 8
6 10
5 7

Sortie 2

233333338

Remarque

Explication de l'exemple : Considérons tous les ordres possibles dans lesquels Radek analysera les robinets dans le premier exemple :

• Pour l'ordre 1, 2, 3, il ouvrira les 3 robinets.
• Pour l'ordre 1, 3, 2, il ouvrira le premier et le troisième robinet. Après l'ouverture du troisième robinet, l'eau inondera également la deuxième étagère, il n'a donc plus besoin d'ouvrir le deuxième robinet.
• Pour l'ordre 2, 1, 3, il ouvrira les 3 robinets.
• Pour l'ordre 2, 3, 1, il ouvrira le deuxième et le troisième robinet. Après l'ouverture du troisième robinet, l'eau inondera la première étagère, il n'est donc pas nécessaire d'ouvrir le premier robinet.
• Pour les ordres 3, 1, 2 et 3, 2, 1, il n'ouvrira que le troisième robinet. Après son ouverture, toutes les étagères seront inondées, il n'est donc pas nécessaire d'ouvrir les autres robinets.

En moyenne, Radek doit donc ouvrir $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$ robinets.

Dans le deuxième exemple, Radek doit ouvrir en moyenne $\frac{91}{30}$ robinets. Comme $30^{-1} \equiv 233333335 \pmod{10^9 + 7}$, nous avons $91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9 + 7}$.