Farmer John hat $N$ Kühe auf seinem Hof ($2 \leq N \leq 2\cdot 10^5$), die praktischerweise mit $1 \dots N$ nummeriert sind. Kuh $i$ befindet sich an den ganzzahligen Koordinaten $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John möchte zwei Teams für eine Partie Mooball auswählen!

Eines der Teams ist das „rote“ Team, das andere das „blaue“ Team. Für die Teams gibt es nur wenige Anforderungen. Kein Team darf leer sein, und jede der $N$ Kühe darf höchstens einem Team angehören (möglicherweise keinem). Die einzige weitere Anforderung ergibt sich aus einer Besonderheit von Mooball: einem unendlich langen Netz, das als horizontale oder vertikale Gerade in der Ebene an einer nicht ganzzahligen Koordinate, etwa $x = 0.5$, aufgestellt werden muss. FJ muss die Teams so auswählen, dass sie durch ein Netz getrennt werden können. Die Kühe sind nicht bereit, sich dafür zu bewegen.

Hilf dem Farmer! Berechne für Farmer John die Anzahl der Möglichkeiten, ein rotes und ein blaues Team auszuwählen, die die obigen Anforderungen erfüllen, modulo $10^9+7$.

Eingabe

Die erste Eingabezeile enthält eine einzelne ganze Zahl $N.$

Die nächsten $N$ Eingabezeilen enthalten jeweils zwei durch ein Leerzeichen getrennte ganze Zahlen $x_i$ und $y_i$. Es ist garantiert, dass die $x_i$ eine Permutation von $1\dots N$ bilden; dasselbe gilt für die $y_i$.

Ausgabe

Eine einzelne ganze Zahl, die die Anzahl der Möglichkeiten angibt, ein rotes und ein blaues Team auszuwählen, die die obigen Anforderungen erfüllen, modulo $10^9+7$.

Beispiele

Eingabe 1

2
1 2
2 1

Ausgabe 1

2

Hinweis

Wir können entweder Kuh 1 dem roten Team und Kuh 2 dem blauen Team zuordnen oder umgekehrt. In beiden Fällen können wir die Teams durch ein Netz trennen (beispielsweise $x=1.5$).

Eingabe 2

3
1 1
2 2
3 3

Ausgabe 2

10

Hinweis

Hier sind alle zehn möglichen Zuordnungen der Kühe zu Teams. Das $i$-te Zeichen bezeichnet das Team der $i$-ten Kuh oder ist . , wenn die $i$-te Kuh keinem Team angehört.

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

Eingabe 3

3
1 1
2 3
3 2

Ausgabe 3

12

Hinweis

Hier sind alle zwölf möglichen Zuordnungen der Kühe zu Teams:

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

Eingabe 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

Ausgabe 4

441563023

Hinweis

Achte darauf, die Antwort modulo $10^9+7$ auszugeben.

Teilaufgaben

• Eingabe 5: $N\le 10$
• Eingaben 6–9: $N\le 200$
• Eingaben 10–13: $N\le 3000$
• Eingaben 14–24: Keine zusätzlichen Beschränkungen.

Aufgabenautor: Dhruv Rohatgi