Farmer John possède $N$ vaches dans sa ferme ($2 \leq N \leq 2\cdot 10^5$), numérotées commodément de $1 \dots N$. La vache $i$ se trouve aux coordonnées entières $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John souhaite choisir deux équipes pour une partie de mooball !

Une équipe sera l'équipe « rouge », et l'autre l'équipe « bleue ». Les équipes ne doivent respecter que quelques exigences. Aucune équipe ne peut être vide, et chacune des $N$ vaches doit appartenir à au plus une équipe (éventuellement aucune). La seule autre exigence découle d'une particularité du mooball : un filet infiniment long, qui doit être placé suivant une droite horizontale ou verticale du plan à une coordonnée non entière, par exemple $x = 0.5$. FJ doit choisir les équipes de manière à pouvoir les séparer par un filet. Les vaches refusent de se déplacer pour rendre cela possible.

Aidez ce fermier ! Calculez pour Farmer John le nombre de façons de choisir une équipe rouge et une équipe bleue satisfaisant les exigences ci-dessus, modulo $10^9+7$.

Entrée

La première ligne de l'entrée contient un unique entier $N.$

Chacune des $N$ lignes suivantes de l'entrée contient deux entiers $x_i$ et $y_i$ séparés par une espace. Il est garanti que les $x_i$ forment une permutation de $1\dots N$, et il en va de même pour les $y_i$.

Sortie

Un unique entier indiquant le nombre de façons de choisir une équipe rouge et une équipe bleue satisfaisant les exigences ci-dessus, modulo $10^9+7$.

Exemples

Entrée 1

2
1 2
2 1

Sortie 1

2

Remarque

Nous pouvons choisir la vache 1 pour l'équipe rouge et la vache 2 pour l'équipe bleue, ou l'inverse. Dans les deux cas, nous pouvons séparer les deux équipes par un filet (par exemple, $x=1.5$).

Entrée 2

3
1 1
2 2
3 3

Sortie 2

10

Remarque

Voici les dix façons possibles de répartir les vaches dans les équipes ; le $i$-ième caractère indique l'équipe de la $i$-ième vache, ou . si elle n'appartient à aucune équipe.

RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR

Entrée 3

3
1 1
2 3
3 2

Sortie 3

12

Remarque

Voici les douze façons possibles de répartir les vaches dans les équipes :

RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR

Entrée 4

40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40

Sortie 4

441563023

Remarque

Veillez à afficher la réponse modulo $10^9+7$.

Sous-tâches

• Entrée 5 : $N\le 10$
• Entrées 6–9 : $N\le 200$
• Entrées 10–13 : $N\le 3000$
• Entrées 14–24 : aucune contrainte supplémentaire.

Auteur du problème : Dhruv Rohatgi