Farmer John tem $N$ vacas em sua fazenda ($2 \leq N \leq 2\cdot 10^5$), convenientemente numeradas de $1 \dots N$. A vaca $i$ está nas coordenadas inteiras $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John quer escolher duas equipes para uma partida de mooball!

Uma das equipes será a equipe “vermelha”; a outra será a equipe “azul”. Há apenas alguns requisitos para as equipes. Nenhuma delas pode estar vazia, e cada uma das $N$ vacas deve estar em no máximo uma equipe (possivelmente em nenhuma). O único outro requisito decorre de uma característica única do mooball: uma rede infinitamente longa, que deve ser colocada como uma reta horizontal ou vertical no plano, em uma coordenada não inteira, como $x = 0.5$. FJ deve escolher as equipes de modo que seja possível separá-las por uma rede. As vacas não estão dispostas a se mover para tornar isso possível.

Ajude o fazendeiro! Calcule para Farmer John o número de maneiras de escolher uma equipe vermelha e uma equipe azul que satisfaçam os requisitos acima, módulo $10^9+7$.

Entrada

A primeira linha da entrada contém um único inteiro $N.$

Cada uma das próximas $N$ linhas da entrada contém dois inteiros separados por espaços, $x_i$ e $y_i$. É garantido que os $x_i$ formam uma permutação de $1\dots N$, e o mesmo vale para os $y_i$.

Saída

Um único inteiro que indica o número de maneiras de escolher uma equipe vermelha e uma equipe azul que satisfaçam os requisitos acima, módulo $10^9+7$.

Exemplos

Entrada 1

2
1 2
2 1

Saída 1

2

Explicação

Podemos escolher a vaca 1 para a equipe vermelha e a vaca 2 para a equipe azul, ou o contrário. Em ambos os casos, podemos separar as duas equipes por uma rede (por exemplo, $x=1.5$).

Entrada 2

3
1 1
2 2
3 3

Saída 2

10

Explicação

Aqui estão todas as dez maneiras possíveis de distribuir as vacas nas equipes; o $i$-ésimo caractere indica a equipe da $i$-ésima vaca, ou . se a $i$-ésima vaca não pertence a nenhuma equipe.

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

Entrada 3

3
1 1
2 3
3 2

Saída 3

12

Explicação

Aqui estão todas as doze maneiras possíveis de distribuir as vacas nas equipes:

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

Entrada 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

Saída 4

441563023

Explicação

Certifique-se de imprimir a resposta módulo $10^9+7$.

Subtarefas

• Teste 5: $N\le 10$
• Testes 6–9: $N\le 200$
• Testes 10–13: $N\le 3000$
• Testes 14–24: Nenhuma restrição adicional.

Autor do problema: Dhruv Rohatgi