Muchos contenedores son transportados por barcos al puerto todos los días. Ellos son transportados alrededor de todo el país por camiones. El puerto es muy estrecho por lo que solo tiene dos áreas donde poner contenedores. En cada área se puede poner cualquier cantidad de contenedor verticalmente. Por razones de seguridad, cuando un contenedor es transportado por un barco hay que ponerlo en una de las dos áreas. Si ya hay contenedores puestos ahi previamente entonces el contenedor actual se pone encima de estos. Cuando transportamos un contenedor en camión hay que tomar el contenedor de la cima de cualquiera de las dos áreas.

Hoy ~N~ contenedores están siendo transportados al puerto. Todos ellos seran transportados por camiones. Tu tarea es facilitar esta tarea al puerto. Para cada contenedor conoces cuando entra y cuando sale. Escribe un programa que calcule el número de maneras de poner los contenedores módulo ~10^9+7~.

Tarea:

Dado el número de contenedores transportados al puerto y el tiempo en que llega y se va cada uno, escribe un programa que calcule el número de maneras de poner y quitar los contenedores tal que satisfaga las condiciones módulo ~10^9+7~.

Entrada:

La primera línea contiene un entero ~N~, el número de contenedores transportados al puerto. Las siguientes ~2N~ líneas contienen dos enteros separados por espacio: ~A_i~, ~B_i~. Esto significa que el ~i~-ésimo contenedor debe entrar al puerto en el momento ~A_i~ y salir al momento ~B_i~.

Salida:

La salida contiene un único número: La cantidad de maneras de poner y quitar los contenedores satisfaciendo las condiciones módulo ~10^9+7~.

Limites:

Todos los datos de entrada satisfacen las siguientes condiciones.

~1 \leq N \leq 10^6.~

~1 \leq A_i \leq 2N~ ~(1 \leq i \leq N).~

~1 \leq B_i \leq 2N~ ~(1 \leq i \leq N).~

~A_i \leq B_i~ ~(1 \leq i \leq N).~

Los ~2N~ enteros ~A_1, \dots , A_n, B_1, \dots, B_n~ son diferentes entre ellos.

Subtarea 1 (10 puntos):

~N \leq 20.~

Subtarea 2 (12 puntos):

~N \leq 2000.~

Subtarea 3 (56 puntos):

~N \leq 10^5.~

Subtask 4 (22 puntos):

Sin restricciones adicionales.

Entrada de ejemplo 1:

4
1 3
2 5
4 8
6 7

Salida de ejemplo 1:

4

Hay cuatro formas de poner y quitar los contenedores. Denotemos las áreas como ~A~ y ~B~. Las siguientes formas de poner los contenedores satisfacen las condiciones.

Poner el ~1~, ~2~, ~3~ y ~4~ contenedor en las áreas ~A~, ~B~, ~A~, ~A~ respectivamente.

Poner el ~1~, ~2~, ~3~ y ~4~ contenedor en las áreas ~A~, ~B~, ~A~, ~B~ respectivamente.

Poner el ~1~, ~2~, ~3~ y ~4~ contenedor en las áreas ~B~, ~A~, ~B~, ~A~ respectivamente.

Poner el ~1~, ~2~, ~3~ y ~4~ contenedor en las áreas ~B~, ~A~, ~B~, ~B~ respectivamente.

Entrada de ejemplo 2:

3
1 4
2 5
3 6

Salida de ejemplo 2:

0

Entrada de ejemplo 3:

5
1 4
2 10
6 9
7 8
3 5

Salida de ejemplo 3:

8

Entrada de ejemplo 4:

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12

Salida de ejemplo 4:

16