문제

Farmer John has $N$ cows on his farm ($2 \leq N \leq 2\cdot 10^5$), conveniently numbered $1 \dots N$. Cow $i$ is located at integer coordinates $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John wants to pick two teams for a game of mooball!

One of the teams will be the "red" team; the other team will be the "blue" team. There are only a few requirements for the teams. Neither team can be empty, and each of the $N$ cows must be on at most one team (possibly neither). The only other requirement is due to a unique feature of mooball: an infinitely long net, which must be placed as either a horizontal or vertical line in the plane at a non-integer coordinate, such as $x = 0.5$. FJ must pick teams so that it is possible to separate the teams by a net. The cows are unwilling to move to make this true.

Help a farmer out! Compute for Farmer John the number of ways to pick a red team and a blue team satisfying the above requirements, modulo $10^9+7$.

입력

The first line of input contains a single integer $N.$

The next $N$ lines of input each contain two space-separated integers $x_i$ and $y_i$. It is guaranteed that the $x_i$ form a permutation of $1\dots N$, and same for the $y_i$.

출력

A single integer denoting the number of ways to pick a red team and a blue team satisfying the above requirements, modulo $10^9+7$.

예제 입력 1

2
1 2
2 1

예제 출력 1

2

예제 입력 2

3
1 1
2 2
3 3

예제 출력 2

10

예제 입력 3

3
1 1
2 3
3 2

예제 출력 3

12

예제 입력 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

예제 출력 4

441563023

점수

Input 5: $N\le 10$Inputs 6-9: $N\le 200$Inputs 10-13: $N\le 3000$Inputs 14-24: No additional constraints.