На ферме 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