Farmer John ha $N$ mucche nella sua fattoria ($2 \leq N \leq 2\cdot 10^5$), comodamente numerate $1 \dots N$. La mucca $i$ si trova alle coordinate intere $(x_i, y_i)$ ($1\le x_i,y_i\le N$). Farmer John vuole scegliere due squadre per una partita di mooball!

Una delle squadre sarà la squadra "rossa"; l'altra sarà la squadra "blu". Ci sono solo pochi requisiti per le squadre. Nessuna squadra può essere vuota, e ciascuna delle $N$ mucche deve appartenere al massimo a una squadra (eventualmente a nessuna). L'unico altro requisito deriva da una caratteristica particolare del mooball: una rete infinitamente lunga, che deve essere collocata come retta orizzontale o verticale nel piano a una coordinata non intera, per esempio $x = 0.5$. FJ deve scegliere le squadre in modo che sia possibile separarle con una rete. Le mucche non sono disposte a spostarsi per rendere ciò possibile.

Dai una mano a un contadino! Calcola per Farmer John il numero di modi di scegliere una squadra rossa e una squadra blu che soddisfino i requisiti sopra indicati, modulo $10^9+7$.

Input

La prima riga di input contiene un solo intero $N.$

Ciascuna delle successive $N$ righe di input contiene due interi $x_i$ e $y_i$ separati da uno spazio. È garantito che gli $x_i$ formino una permutazione di $1\dots N$, e lo stesso vale per gli $y_i$.

Output

Un solo intero che indica il numero di modi di scegliere una squadra rossa e una squadra blu che soddisfino i requisiti sopra indicati, modulo $10^9+7$.

Esempi

Input 1

2
1 2
2 1

Output 1

2

Nota

Possiamo scegliere la mucca 1 come squadra rossa e la mucca 2 come squadra blu, oppure viceversa. In entrambi i casi possiamo separare le due squadre con una rete (per esempio $x=1.5$).

Input 2

3
1 1
2 2
3 3

Output 2

10

Nota

Ecco tutti i dieci modi possibili di assegnare le mucche alle squadre; l'$i$-esimo carattere indica la squadra dell'$i$-esima mucca, oppure . se l'$i$-esima mucca non appartiene a nessuna squadra.

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

Input 3

3
1 1
2 3
3 2

Output 3

12

Nota

Ecco tutti i dodici modi possibili di assegnare le mucche alle squadre:

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

Input 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

Output 4

441563023

Nota

Assicurati di stampare la risposta modulo $10^9+7$.

Sottoproblemi

• Caso di test 5: $N\le 10$
• Casi di test 6–9: $N\le 200$
• Casi di test 10–13: $N\le 3000$
• Casi di test 14–24: Nessun vincolo aggiuntivo.

Autore del problema: Dhruv Rohatgi