Botes en Festival


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 64M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

En la ciudad de Teherán, existe un río imaginario llamado ByteRiver en el que sus aguas corren en dirección este-oeste. En la orilla norte del río hay N escuelas para aprender a remar numeradas desde 1 hasta N así que usted puede moverse desde el extremo oeste al extremo más al este de la orilla. Todos los botes de la misma escuela tienen exactamente el mismo color por lo que son indistinguibles. Los botes de diferentes escuelas siempre tienen diferentes colores y siempre son distinguibles. La escuela numerada i puede elegir no enviar botes al famoso festival de tradiciones persas. Si una escuela elige enviar botes al festival pueden enviar cualquier número de botes entre a_i y b_i, inclusive (a_i \leq b_i).

Una condición clave es que el número de botes enviados por la escuela número i, si ha decidido enviar algún bote, debe ser más grande que el número de botes enviados por alguna escuela numerada menor que i, si alguna de tales escuelas ha elegido enviar botes.

Dados los a_i y b_i para todas las escuelas, encuentre el número de todas las posibles maneras que las escuelas pueden enviar botes al festival, bajo la condición que al menos una escuela eligió enviar botes.

Entrada

La primera línea de la entrada contiene un entero simple N - el número de escuelas. La i-ésima escuela de las próximas N líneas contienen dos enteros a_i y b_i (1 \leq a_i \leq b_i \leq 10^9)

Salida

La única línea de la salida contiene el resto cuando el número de todas los posibles casos en que las escuelas pueden enviar botes al festival es dividido por 1,000,000,007.

Ejemplo de Entrada

2
1 2
2 3

Ejemplo de Salida

7

Explicación del ejemplo: Hay 4 formas donde solamente una escuela envía botes y 3 maneras donde ambas escuelas envían botes entonces la respuesta es 7.

Evaluación

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

  • Subtarea 2 (22 puntos): 1 \leq N \leq 500, \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.

Hay 4 formas donde solamente una escuela envía botes y 3 maneras donde ambas escuelas envían botes entonces la respuesta es 7.


Comments

There are no comments at the moment.