Cais

Cerință

Cum este minunata zi de Sâmbătă, Cais decide să meargă la restaurantul Burgeri și Suc, unde este o oferta de tip All you can eat. El are lângă el două locuri unde poate pune farfuriile cu mâncare în teancuri (A și B). Cais știe că pe bandă vor veni $N$ preparate, cel cu indexul $i$ venind la secunda $s[i]$, iar acesta va alege unul dintre cele două teancuri și va plasa farfuria în vârfului acestuia. La momentul $t[i]$, Cais va dori să mănânce preparatul din farfuria $i$ și o va da jos din vârful teancului. El nu poate să mănânce un preparat decât dacă acesta este plasat în vârful unui teanc la momentul ales. Cais, fiind pasionat de combinatorică, se întreabă: "În câte moduri pot să așez farfuriile cu preparate pe cele două teancuri astfel încât să pot să le mănânc pe toate cele $N$?"
Deoarece numărul poate fi foarte mare acesta dorește doar restul modulo $1 \ 000 \ 000 \ 007$

Date de intrare

Pe prima linie a fișierului de intrare cais.in se găseste un număr întreg, $N$.
Pe linia $i + 1$ se vor află $s[i]$ și $t[i]$ cu semnificația din enunț.

Date de ieșire

Pe prima linie a fișierului de ieșire cais.out se va găși un singur număr întreg, numărul de moduri pentru a așeza farfuriile.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• șirul $s + t$ formează o permutare a numerelor de la $1$ la $2N$
• pentru $12$ de puncte $N \leq 10$
• pentru alte $21$ puncte $N \leq 2 \ 000$
• pentru alte $48$ de puncte $N \leq 100 \ 000$

Exemplul 1

cais.in

4
1 3
2 5
4 8
6 7

cais.out

4

Explicație

ABAA, ABAB, BABA, BABB

Exemplul 2

cais.in

3
1 4
2 5
3 6

cais.out

0

Explicație

Nu există soluție. Cais e supărat.