Le long d'une longue rue se trouvent des lampadaires sur lesquels sont placées $n$ lanternes. Introduisons un système de coordonnées le long de la rue. Le lampadaire sur lequel se trouve la $i$-ème lanterne est situé au point de coordonnée $x_i$. Dans les six premières sous-tâches de ce problème, valant 85 points, deux lanternes ne sont jamais attachées au même lampadaire, c'est-à-dire que toutes les valeurs $x_i$ sont distinctes. Dans les deux dernières sous-tâches, il peut y avoir au plus deux lanternes sur chaque lampadaire.
Pour éclairer la rue, certaines lanternes peuvent être allumées. Une lanterne active d'indice $i$ a une luminosité $s_i$. Elle brille de telle sorte qu'elle illumine un segment continu de la rue de longueur $s_i$ mètres à partir du lampadaire sur lequel elle se trouve. Chaque lanterne active peut être orientée soit vers la gauche, soit vers la droite. Si la $i$-ème lanterne est orientée vers la gauche, elle éclaire le segment de rue $[x_i - s_i, x_i]$, et si elle est orientée vers la droite, alors $[x_i, x_i + s_i]$.
Choisissons un ensemble non vide de lanternes à allumer pour éclairer une section de la rue. Nous appellerons cet ensemble de lanternes économique s'il est possible d'orienter chaque lanterne choisie vers la gauche ou vers la droite de telle sorte que deux conditions soient satisfaites :
- les segments éclairés forment un segment continu de la rue ;
- aucun segment de longueur non nulle n'est éclairé par deux lanternes ou plus simultanément.
La figure ci-dessous montre les sous-ensembles économiques de deux lanternes pour le deuxième exemple de l'énoncé et les manières d'éclairer un segment continu de la rue. La luminosité de chaque lanterne est inscrite au-dessus d'elle.
Trouvez le nombre de sous-ensembles économiques de lanternes. En réponse, affichez le reste de cette valeur modulo $10^9 + 7$.
Entrée
La première ligne contient un seul entier $n$ ($1 \le n \le 10^5$) — le nombre de lanternes. Vient ensuite la description des lanternes.
Chacune des $n$ lignes suivantes contient deux entiers $x_i$ et $s_i$ — la coordonnée du lampadaire où se trouve la $i$-ème lanterne et sa luminosité ($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$).
Il est garanti qu'il y a au plus deux lanternes sur le même lampadaire, c'est-à-dire que pour chaque $v$ il y a au plus deux indices $i$ tels que $x_i = v$.
Sortie
Affichez un seul entier — le reste de la division du nombre de façons de choisir un sous-ensemble économique de lanternes par $10^9 + 7$.
Sous-tâches
Nous introduisons une variable $t$ — le nombre maximal de lanternes pouvant avoir la même coordonnée $x_i$.
Si $t = 1$, alors $x_1 < x_2 < \dots < x_n$.
Si $t = 2$, alors $x_1 \le x_2 \le \dots \le x_n$, et si $x_i = x_{i+1}$, alors $x_{i-1} < x_i$ et $x_{i+1} < x_{i+2}$ (si les lanternes correspondantes existent).
| Sous-tâche | Points | $t$ | $n$ | Contraintes supplémentaires | Sous-tâches requises |
|---|---|---|---|---|---|
| 1 | 10 | $t = 1$ | $n \le 10$ | ||
| 2 | 15 | $t = 1$ | Pour deux lanternes distinctes $i, j$, $x_i - s_i \ne x_j$ et $x_i + s_i \ne x_j - s_j$ | ||
| 3 | 15 | $t = 1$ | Pour deux lanternes distinctes $i, j$, $s_i \ne s_j$ | ||
| 4 | 15 | $t = 1$ | Pour deux lanternes distinctes $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}$, alors $s_i \ne s_{i+1}$ | 1 – 6 | |
| 8 | 5 | $t = 2$ | Exemples, 1 – 7 |
Exemples
Entrée 1
2 2 3 7 2
Sortie 1
3
Entrée 2
3 1 1 3 1 4 2
Sortie 2
6
Entrée 3
5 3 2 4 2 5 2 6 2 7 2
Sortie 3
10
Entrée 4
4 3 2 7 4 7 4 8 2
Sortie 4
8
Entrée 5
5 1 2 1 3 2 1 2 2 4 1
Sortie 5
19
Remarque
Dans le premier exemple, les trois sous-ensembles non vides de lanternes sont économiques.
Dans le deuxième exemple, tous les sous-ensembles de lanternes sont économiques, à l'exception de l'ensemble $\{1, 2, 3\}$.