A lo largo de una calle larga hay postes sobre los cuales se encuentran $n$ faroles. Introduzcamos un sistema de coordenadas a lo largo de la calle. El poste donde se encuentra el $i$-ésimo farol está ubicado en el punto con coordenada $x_i$. En los primeros seis subtareas de este problema, que valen 85 puntos, no hay dos faroles en el mismo poste, es decir, todos los valores de $x_i$ son distintos. En las últimas dos subtareas, puede haber como máximo dos faroles en cada poste.
Para iluminar la calle, se pueden encender algunos faroles. Un farol activo con índice $i$ tiene un brillo $s_i$. Alumbra de tal manera que ilumina un segmento continuo de la calle de longitud $s_i$ metros a partir del poste donde se encuentra. Cada farol activo puede orientarse hacia la izquierda o hacia la derecha. Si el $i$-ésimo farol está dirigido hacia la izquierda, ilumina el segmento de la calle $[x_i - s_i, x_i]$, y si está hacia la derecha, ilumina $[x_i, x_i + s_i]$.
Elijamos un conjunto no vacío de faroles para encender con el fin de iluminar una sección de la calle. Llamaremos a este conjunto de faroles económico si es posible orientar cada farol elegido hacia la izquierda o hacia la derecha de manera que se cumplan dos condiciones:
- los segmentos iluminados forman un segmento continuo de la calle;
- ningún segmento de longitud no nula es iluminado simultáneamente por dos o más faroles.
La figura siguiente muestra los subconjuntos económicos de dos faroles para la segunda muestra del enunciado y las formas de iluminar un segmento continuo de la calle. El brillo de cada farol está escrito sobre él.
Encuentre la cantidad de subconjuntos económicos de faroles. Como respuesta, entregue el resto de este valor módulo $10^9 + 7$.
Entrada
La primera línea contiene un único entero $n$ ($1 \le n \le 10^5$) — el número de faroles. A continuación sigue la descripción de los faroles.
Cada una de las siguientes $n$ líneas contiene dos enteros $x_i$ y $s_i$ — la coordenada del poste donde se encuentra el $i$-ésimo farol y su brillo ($1 \le x_i \le 5 \cdot 10^5$, $1 \le s_i \le 5 \cdot 10^5$, $x_1 \le x_2 \le \dots \le x_n$).
Está garantizado que hay como máximo dos faroles en el mismo poste, es decir, para cada $v$ hay como máximo dos índices $i$ tales que $x_i = v$.
Salida
Entregue un único entero — el resto de la división de la cantidad de formas de elegir un subconjunto económico de faroles entre $10^9 + 7$.
Subtareas
Introducimos una variable $t$ — el número máximo de faroles que pueden tener la misma coordenada $x_i$.
Si $t = 1$, entonces $x_1 < x_2 < \dots < x_n$.
Si $t = 2$, entonces $x_1 \le x_2 \le \dots \le x_n$, y si $x_i = x_{i+1}$, entonces $x_{i-1} < x_i$ y $x_{i+1} < x_{i+2}$ (si los faroles correspondientes existen).
| Subtarea | Puntos | $t$ | $n$ | Restricciones adicionales | Subtareas requeridas |
|---|---|---|---|---|---|
| 1 | 10 | $t = 1$ | $n \le 10$ | ||
| 2 | 15 | $t = 1$ | Para cualquier par de faroles distintos $i, j$, $x_i - s_i \ne x_j$ y $x_i + s_i \ne x_j - s_j$ | ||
| 3 | 15 | $t = 1$ | Para cualquier par de faroles distintos $i, j$, $s_i \ne s_j$ | ||
| 4 | 15 | $t = 1$ | Para cualquier par de faroles distintos $i, j$, $s_i = s_j$ | ||
| 5 | 10 | $t = 1$ | $n \le 1000$ | $s_i, x_i \le 1000$ | |
| 6 | 20 | $t = 1$ | 1 – 5 | ||
| 7 | 10 | $t = 2$ | Si $x_i = x_{i+1}$, entonces $s_i \ne s_{i+1}$ | 1 – 6 | |
| 8 | 5 | $t = 2$ | Ejemplos, 1 – 7 |
Ejemplos
Entrada 1
2 2 3 7 2
Salida 1
3
Entrada 2
3 1 1 3 1 4 2
Salida 2
6
Entrada 3
5 3 2 4 2 5 2 6 2 7 2
Salida 3
10
Entrada 4
4 3 2 7 4 7 4 8 2
Salida 4
8
Entrada 5
5 1 2 1 3 2 1 2 2 4 1
Salida 5
19
Nota
En el primer ejemplo, los tres subconjuntos no vacíos de faroles son económicos.
En el segundo ejemplo, todos los subconjuntos de faroles son económicos, excepto el conjunto $\{1, 2, 3\}$.