Nông trại của nông dân John có tất cả \(N\) (\(2 \leq N \leq 2 \times 10^5\)) con bò, được đánh số từ \(1\) đến \(N\). Những con bò đang đứng hóng gió ở vị trí có tọa độ (\(x_i, y_i\)) trên bản đồ của trang trại mô tả dưới dạng trục hai chiều.

Do những con bò quá lười, nông dân John muốn tổ chức một trò chơi cho chúng. Anh John chia đàn bò thành đội "xanh" và "đỏ" theo những quy tắc sau:

• Không có đội nào không có thành viên.
• Mỗi một con bò thuộc tối đa một đội (có thể là không đội nào)
• Một tấm lưới có độ dài vô tận sẽ được đặt song song với trục tung hoặc trục hoành trên bản đồ trang trại, trên một vị trí không nguyên (ví dụ như \(x = 0.5\))

Nhiệm vụ của bạn là giúp nông dân John chia đàn bò thành hai đội và đặt lưới ở giữa hai đội, biết đàn bò quá lười để di chuyển khỏi vị trí chúng đang ở. Hãy nói cho John biết có tất cả bao nhiêu cách để chọn hai đội sao cho thỏa mãn những điều kiện trên, tính theo modulo \(10^9 +7\).

Input

• Dòng đầu tiên chứa một số nguyên \(N\).
• \(N\) dòng tiếp theo mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(x_i\) và \(y_i\).

Output

• Gồm một số nguyên duy nhất là số cách chọn hai đội xanh và đỏ, modulo \(10^9 + 7\).

Scoring

• Subtask 1: \(N \leq 10\)
• Subtask 2: \(N \leq 200\)
• Subtask 3: \(N \leq 3000\)
• Subtask 4: Không có ràng buộc gì thêm.

Example

2
1 2
2 1

2

3
1 1
2 2
3 3

10

3
1 1
2 3
3 2

12

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

441563023