Farmer John 的農場上有 $N$ 頭牛（$2 \leq N \leq 2\cdot 10^5$），為方便起見，編號為 $1 \dots N$。第 $i$ 頭牛位於整數座標 $(x_i, y_i)$（$1\le x_i,y_i\le N$）。Farmer John 想選出兩支隊伍來進行一場牛球比賽！

其中一支是「紅隊」，另一支是「藍隊」。隊伍只需要滿足幾項要求。兩支隊伍都不能為空，而 $N$ 頭牛中的每一頭最多只能加入一支隊伍（也可以兩支都不加入）。唯一的其他要求來自牛球的一個獨特特徵：一張無限長的球網，它必須放在平面上一條座標為非整數的水平線或垂直線上，例如 $x = 0.5$。FJ 必須選出能夠用一張球網分隔的兩支隊伍。牛們不願意為了達成這個要求而移動。

幫幫這位農夫吧！為 Farmer John 計算選出滿足以上要求的紅隊和藍隊的方法數，並對 $10^9+7$ 取模。

輸入格式

輸入的第一行包含一個整數 $N.$

接下來 $N$ 行，每行包含兩個以空格分隔的整數 $x_i$ 和 $y_i$。保證所有 $x_i$ 構成 $1\dots N$ 的一個排列，所有 $y_i$ 也同樣如此。

輸出格式

輸出一個整數，表示選出滿足以上要求的紅隊和藍隊的方法數，並對 $10^9+7$ 取模。

範例

輸入格式 1

2
1 2
2 1

輸出格式 1

2

說明

我們可以選擇牛 1 為紅隊、牛 2 為藍隊，也可以反過來。在這兩種情況下，都能用一張球網分隔兩支隊伍（例如 $x=1.5$）。

輸入格式 2

3
1 1
2 2
3 3

輸出格式 2

10

說明

以下列出將牛分配到隊伍中的全部十種可能方法；第 $i$ 個字元表示第 $i$ 頭牛所屬的隊伍，若第 $i$ 頭牛沒有加入任何隊伍，則為 .。

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

輸入格式 3

3
1 1
2 3
3 2

輸出格式 3

12

說明

以下列出將牛分配到隊伍中的全部十二種可能方法：

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

輸入格式 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

說明

請務必輸出答案對 $10^9+7$ 取模的結果。

子任務

• 輸入 5：$N\le 10$
• 輸入 6–9：$N\le 200$
• 輸入 10–13：$N\le 3000$
• 輸入 14–24：沒有額外限制。

題目作者：Dhruv Rohatgi