Farmer John tiene $N$ vacas en su granja ($2 \leq N \leq 2\cdot 10^5$), numeradas convenientemente de $1 \dots N$. La vaca $i$ está en las coordenadas enteras $(x_i, y_i)$ ($1\le x_i,y_i\le N$). ¡Farmer John quiere elegir dos equipos para una partida de mooball!

Uno de los equipos será el equipo «rojo» y el otro será el equipo «azul». Solo hay unos pocos requisitos. Ningún equipo puede estar vacío, y cada una de las $N$ vacas debe pertenecer como máximo a un equipo (puede no pertenecer a ninguno). El único requisito adicional se debe a una característica singular del mooball: una red infinitamente larga, que debe colocarse como una recta horizontal o vertical en el plano en una coordenada no entera, como $x = 0.5$. FJ debe elegir los equipos de modo que sea posible separarlos con una red. Las vacas no están dispuestas a moverse para que esto sea posible.

¡Ayuda al granjero! Calcula para Farmer John el número de formas de elegir un equipo rojo y uno azul que satisfagan los requisitos anteriores, módulo $10^9+7$.

Entrada

La primera línea de entrada contiene un único entero $N.$

Cada una de las siguientes $N$ líneas contiene dos enteros $x_i$ e $y_i$ separados por un espacio. Se garantiza que los $x_i$ forman una permutación de $1\dots N$, y lo mismo sucede con los $y_i$.

Salida

Un único entero que indique el número de formas de elegir un equipo rojo y uno azul que satisfagan los requisitos anteriores, módulo $10^9+7$.

Ejemplos

Entrada 1

2
1 2
2 1

Salida 1

2

Nota

Podemos elegir que la vaca 1 forme el equipo rojo y la vaca 2 el azul, o al revés. En ambos casos, podemos separar los equipos con una red (por ejemplo, $x=1.5$).

Entrada 2

3
1 1
2 2
3 3

Salida 2

10

Nota

Estas son las diez formas posibles de asignar las vacas a los equipos; el $i$-ésimo carácter indica el equipo de la $i$-ésima vaca, o . si esa vaca no está en ningún equipo.

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

Entrada 3

3
1 1
2 3
3 2

Salida 3

12

Nota

Estas son las doce formas posibles de asignar las vacas a los equipos:

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

Salida 4

441563023

Nota

Asegúrate de imprimir la respuesta módulo $10^9+7$.

Subtareas

• Entrada 5: $N\le 10$
• Entradas 6–9: $N\le 200$
• Entradas 10–13: $N\le 3000$
• Entradas 14–24: Sin restricciones adicionales.

Autor del problema: Dhruv Rohatgi