Problem Description

Farmer John has $N$ cows ($2 \le N \le 2 \cdot 10^5$) on his farm, numbered from $1$ to $N$. Cow $i$ is located at integer coordinates $(x_i, y_i)$ ($1 \le x_i, y_i \le N$). Farmer John wants to select two teams to play a game of Mooball!

One team will be the "Red Team"; the other will be the "Blue Team". There are only a few requirements for team selection. Neither team can be empty, and each of the $N$ cows can be in at most one team (or in neither team). The only other requirement is based on the unique characteristics of Mooball: an infinitely long net, which must be placed as a horizontal or vertical line at non-integer coordinates in the plane, such as $x=0.5$. FJ's team selection must ensure that the two teams can be separated by this net. The cows are unwilling to move for this purpose.

Help Farmer John! Calculate the number of ways to select the Red and Blue teams that meet the above requirements, modulo $10^9+7$.

Input Format

The first line of input contains an integer $N$.

The next $N$ lines each contain two space-separated integers $x_i$ and $y_i$. The input guarantees that $x_i$ forms a permutation of $1 \ldots N$, and similarly for $y_i$.

Output Format

Output a single integer, the number of ways to select the Red and Blue teams that meet the above requirements, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

2
1 2
2 1

Sample Output #1

2

Sample Input #2

3
1 1
2 2
3 3

Sample Output #2

10

Sample Input #3

3
1 1
2 3
3 2

Sample Output #3

12

Sample Input #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

Sample Output #4

441563023

Notes/Hints

Sample Explanation 1

We can choose the Red Team as cow 1 and the Blue Team as cow 2, or vice versa. In either case, we can separate the two teams with a net (e.g., $x=1.5$).

Sample Explanation 2

Here are all ten possible ways to divide the cows into teams; the $i$-th character represents the team of the $i$-th cow, with R for Red, B for Blue, or . for no team.

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

Sample Explanation 3

Here are all twelve possible ways to divide the cows into teams:

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

Sample Explanation 4

Ensure the output is modulo $10^9+7$.

Test Case Properties

• Test case $5$: $N \le 10$.
• Test cases $6-9$: $N \le 200$.
• Test cases $10-13$: $N \le 3000$.
• Test cases $14-24$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分