Farmer John có $N$ con bò trong trang trại ($2 \leq N \leq 2\cdot 10^5$), được đánh số thuận tiện từ $1 \dots N$. Bò $i$ nằm tại tọa độ nguyên $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John muốn chọn hai đội để chơi mooball!

Một đội sẽ là đội «đỏ», đội còn lại sẽ là đội «xanh». Chỉ có một vài yêu cầu đối với các đội. Không đội nào được rỗng, và mỗi con trong $N$ con bò phải thuộc nhiều nhất một đội (có thể không thuộc đội nào). Yêu cầu duy nhất khác xuất phát từ một đặc điểm độc đáo của mooball: một tấm lưới dài vô hạn, phải được đặt thành một đường thẳng nằm ngang hoặc thẳng đứng trong mặt phẳng tại một tọa độ không nguyên, chẳng hạn $x = 0.5$. FJ phải chọn các đội sao cho có thể ngăn cách chúng bằng một tấm lưới. Các con bò không muốn di chuyển để làm điều này trở nên khả thi.

Hãy giúp người nông dân! Tính cho Farmer John số cách chọn một đội đỏ và một đội xanh thỏa mãn các yêu cầu trên, lấy modulo $10^9+7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $N.$

Mỗi dòng trong $N$ dòng tiếp theo của dữ liệu vào chứa hai số nguyên $x_i$ và $y_i$ cách nhau bởi dấu cách. Đảm bảo các $x_i$ tạo thành một hoán vị của $1\dots N$, và các $y_i$ cũng vậy.

Dữ liệu ra

Một số nguyên duy nhất biểu thị số cách chọn một đội đỏ và một đội xanh thỏa mãn các yêu cầu trên, lấy modulo $10^9+7$.

Ví dụ

Dữ liệu vào 1

2
1 2
2 1

Dữ liệu ra 1

2

Ghi chú

Ta có thể chọn bò 1 vào đội đỏ và bò 2 vào đội xanh, hoặc ngược lại. Trong cả hai trường hợp, ta đều có thể ngăn cách hai đội bằng một tấm lưới (chẳng hạn $x=1.5$).

Dữ liệu vào 2

3
1 1
2 2
3 3

Dữ liệu ra 2

10

Ghi chú

Dưới đây là tất cả mười cách có thể phân bò vào các đội; ký tự thứ $i$ biểu thị đội của bò thứ $i$, hoặc . nếu bò thứ $i$ không thuộc đội nào.

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

Dữ liệu vào 3

3
1 1
2 3
3 2

Dữ liệu ra 3

12

Ghi chú

Dưới đây là tất cả mười hai cách có thể phân bò vào các đội:

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

Dữ liệu vào 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

Dữ liệu ra 4

441563023

Ghi chú

Hãy nhớ xuất đáp án lấy modulo $10^9+7$.

Nhiệm vụ con

• Dữ liệu vào 5: $N\le 10$
• Dữ liệu vào 6-9: $N\le 200$
• Dữ liệu vào 10-13: $N\le 3000$
• Dữ liệu vào 14-24: không có giới hạn bổ sung.

Tác giả bài toán: Dhruv Rohatgi