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 は mooball の試合のために 2 つのチームを選びたいと考えています！

一方は「赤」チーム、もう一方は「青」チームです。チームにはいくつかの条件があります。どちらのチームも空であってはならず、$N$ 頭の牛のそれぞれは高々 1 つのチームに所属しなければなりません（どちらにも所属しなくてもかまいません）。残る条件は、mooball 特有の道具、無限に長いネットによるものです。このネットは、平面上の水平または垂直な直線として、$x = 0.5$ のような整数ではない座標に置かなければなりません。FJ は、ネットで 2 つのチームを分離できるようにチームを選ばなければなりません。牛たちは、そのために移動するつもりはありません。

農家を助けてあげましょう！上の条件を満たす赤チームと青チームの選び方の個数を、$10^9+7$ で割った余りを Farmer John のために求めてください。

入力

入力の最初の行には 1 つの整数 $N.$ が与えられます。

続く $N$ 行には、それぞれ空白で区切られた 2 つの整数 $x_i$ と $y_i$ が与えられます。$x_i$ は $1\dots N$ の順列をなし、$y_i$ についても同様であることが保証されます。

出力

上の条件を満たす赤チームと青チームの選び方の個数を、$10^9+7$ で割った余りを表す 1 つの整数を出力してください。

入出力例

入力 1

2
1 2
2 1

出力 1

2

注記

赤チームを牛 1、青チームを牛 2 とするか、その逆にすることができます。どちらの場合も、ネット（例えば $x=1.5$）で 2 つのチームを分離できます。

入力 2

3
1 1
2 2
3 3

出力 2

10

注記

牛をチームに割り当てる 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

注記

牛をチームに割り当てる 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