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 경기를 위해 두 팀을 고르려고 한다!

한 팀은 "빨간" 팀이고 다른 팀은 "파란" 팀이다. 팀에 대한 조건은 몇 가지뿐이다. 어느 팀도 비어 있으면 안 되며, $N$마리의 소는 각각 최대 한 팀에만 속해야 한다 (어느 팀에도 속하지 않을 수도 있다). 나머지 조건은 mooball의 독특한 특징인 무한히 긴 네트 때문이다. 네트는 $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