Farmer John ma na swojej farmie $N$ krów ($2 \leq N \leq 2\cdot 10^5$), dla wygody ponumerowanych $1 \dots N$. Krowa $i$ znajduje się w punkcie o całkowitych współrzędnych $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John chce wybrać dwie drużyny do gry w mooball!

Jedna z drużyn będzie „czerwona”, a druga „niebieska”. Drużyny muszą spełniać tylko kilka wymagań. Żadna nie może być pusta, a każda z $N$ krów może należeć do co najwyżej jednej drużyny (może też nie należeć do żadnej). Jedyne pozostałe wymaganie wynika z wyjątkowej cechy mooballa: nieskończenie długiej siatki, którą należy umieścić na płaszczyźnie jako prostą poziomą lub pionową o niecałkowitej współrzędnej, na przykład $x = 0.5$. FJ musi wybrać drużyny tak, aby dało się je rozdzielić siatką. Krowy nie chcą się przesuwać, żeby to umożliwić.

Pomóż farmerowi! Oblicz dla Farmer John liczbę sposobów wybrania czerwonej i niebieskiej drużyny spełniających powyższe wymagania, modulo $10^9+7$.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $N.$

Każdy z kolejnych $N$ wierszy wejścia zawiera dwie liczby całkowite $x_i$ i $y_i$, oddzielone spacją. Gwarantuje się, że wartości $x_i$ tworzą permutację $1\dots N$; to samo dotyczy wartości $y_i$.

Wyjście

Jedna liczba całkowita oznaczająca liczbę sposobów wybrania czerwonej i niebieskiej drużyny spełniających powyższe wymagania, modulo $10^9+7$.

Przykład

Wejście 1

2
1 2
2 1

Wyjście 1

2

Uwagi

Możemy wybrać krowę 1 do czerwonej drużyny i krowę 2 do niebieskiej, albo odwrotnie. W obu przypadkach możemy rozdzielić drużyny siatką (na przykład $x=1.5$).

Wejście 2

3
1 1
2 2
3 3

Wyjście 2

10

Uwagi

Oto wszystkie dziesięć możliwych sposobów przydzielenia krów do drużyn; $i$-ty znak oznacza drużynę $i$-tej krowy albo . jeśli $i$-ta krowa nie należy do żadnej drużyny.

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

Wejście 3

3
1 1
2 3
3 2

Wyjście 3

12

Uwagi

Oto wszystkie dwanaście możliwych sposobów przydzielenia krów do drużyn:

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

Wejście 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

Wyjście 4

441563023

Uwagi

Pamiętaj, aby wypisać odpowiedź modulo $10^9+7$.

Podzadania

• Test 5: $N\le 10$.
• Testy 6–9: $N\le 200$.
• Testy 10–13: $N\le 3000$.
• Testy 14–24: brak dodatkowych ograniczeń.

Autor zadania: Dhruv Rohatgi