Existe un río llamado Byte River que fluye en dirección este-oeste. En la orilla norte del río hay ~N~ escuelas de navegación numeradas de ~1~ a ~N~ desde el extremo oeste hasta el extremo este de la orilla. Todos los barcos de la misma escuela tienen exactamente el mismo color y, por lo tanto, son indistinguibles. Los barcos de diferentes escuelas siempre tienen colores diferentes y, por lo tanto, son siempre distinguibles. La escuela ~i~ puede optar por no enviar barcos al festival. Si decide enviar barcos al festival, puede enviar cualquier número de barcos desde ~a_i~ hasta ~b_i~, inclusive. (~a_i \leq b_i~)

Una condición clave es que el número de barcos enviados por la escuela numerada ~i~, si ha optado por enviar barcos, debe ser mayor que el número de barcos enviados por cualquier escuela numerada menor que ~i~, si alguna de esas escuelas ha optado por enviar barcos.

Dados ~a_i~ y ~b_i~ para cada escuela, encuentra la cantidad de formas posibles en que las escuelas pueden enviar barcos al festival, bajo la condición de que al menos una escuela elija enviar barcos.

Entrada

La primera linea de entrada contiene un solo entero ~N~ - El número de escuelas.

La ~i~-esima línea de las siguientes ~N~ líneas contiene dos enteros ~a_i~ y ~b_i~. (~1 \leq a_i \leq b_i \leq 10^9~)

Salida

La salida consiste de un solo entero, el resto de dividir la cantidad de formas posibles en que las escuelas pueden enviar barcos al festival por ~10^9+7~

Subtareas

Subtarea 1 (9 puntos): ~1 \leq N \leq 500~ y para todo ~1 \leq i \leq N~, ~a_i = b_i~ .

Subtarea 2 (22 puntos): ~1 \leq N \leq 500~ y ~\sum_{1 \leq i \leq N}{(b_i - a_i) \leq 10^6}~.

Subtarea 3 (27 puntos): ~1 \leq N \leq 100~.

Subtarea 4 (42 puntos): ~1 \leq N \leq 500~.

Entrada Ejemplo:

2
1 2
2 3

Salida Ejemplo:

7

Comentarios

Hay ~4~ formas donde solo una escuela envia botes y ~3~ formas donde ambas escuelas envian botes. Por lo tanto la respuesta es ~7~.