En los concursos de programación, los castores resuelven los problemas en orden, del primero al último. Los revaebs, por otro lado, son un tipo especial de roedor que resuelve los problemas en orden inverso, del último al primero.

¡$N$ castores y $N$ revaebs competirán entre sí en el próximo concurso de programación! El concurso consta de $N$ problemas, donde el problema $k$-ésimo tiene un valor en puntos entero $p_k$ entre $l_k$ y $r_k$, inclusive. La puntuación de un concursante es la suma de los valores en puntos de los problemas que resuelve.

El día del concurso, se sabe que el castor $i$-ésimo resolvió los primeros $i$ problemas, y el revaeb $j$-ésimo resolvió los últimos $j$ problemas. Además, el único par de concursantes con la misma puntuación son los dos que resolvieron todos los problemas, el castor $N$-ésimo y el revaeb $N$-ésimo. Dada esta información, cuente el número de posibles asignaciones de valores en puntos a los problemas del concurso. Dado que este número puede ser grande, imprima su resto al dividirlo por $10^9 + 7$.

Entrada

La primera línea contiene $N$ ($1 \leq N \leq 50$), el número de problemas en el concurso.

Siguen $N$ líneas. La $k$-ésima de estas líneas contiene dos enteros separados por espacios, $l_k$ y $r_k$ ($1 \le l_k \le r_k \le 2000$).

Salida

Imprima una línea que contenga la respuesta: el número de secuencias de valores en puntos módulo $10^9+7$.

Subtareas

• ($10$ puntos) $N \leq 8$ y $r_k \leq 8$ para todo $k$.
• ($30$ puntos) $l_k = 1$ para todo $k$ y existe un $R$ fijo tal que $r_k = R$ para todo $k$.
• ($30$ puntos) $r_k \leq 100$ para todo $k$.
• ($30$ puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

4
1 1
2 2
3 3
10 10

Salida 1

1

Entrada 2

1
1 2000

Salida 2

2000

Entrada 3

4
1 2
1 2
1 2
1 2

Salida 3

2

Entrada 4

5
1 3
2 4
1 4
1 2
3 3

Salida 4

18

Entrada 5

6
1 5
1 5
1 5
1 5
1 5
1 5

Salida 5

5120

Nota

Explicación del ejemplo 1

Los valores en puntos de los problemas solo pueden ser $1, 2, 3, 10$. Usando estos valores, las puntuaciones de los castores son $1, 3, 6, 16$ respectivamente y las puntuaciones de los revaebs son $10, 13, 15, 16$ respectivamente. Todas estas son diferentes, excepto la puntuación de $16$ obtenida por el $4^{\text{o}}$ castor y el $4^{\text{o}}$ revaeb, por lo que esta secuencia es válida, lo que hace que la respuesta sea $1$.

Explicación del ejemplo 2

Este ejemplo satisface las restricciones de la segunda subtarea.

Explicación del ejemplo 3

Este ejemplo satisface las restricciones de la segunda subtarea.

Las únicas secuencias válidas de valores en puntos son $1, 2, 2, 2$ y $2, 2, 2, 1$, lo que hace que la respuesta sea $2$.

Explicación del ejemplo 5

Este ejemplo satisface las restricciones de la segunda subtarea.