Wzdłuż długiej ulicy znajdują się latarnie, na których umieszczonych jest $n$ lamp. Wprowadźmy układ współrzędnych wzdłuż ulicy. Słup, na którym znajduje się $i$-ta lampa, jest umieszczony w punkcie o współrzędnej $x_i$. W pierwszych sześciu podzadaniach tego problemu, wartych 85 punktów, żadne dwie lampy nie są przymocowane do tego samego słupa, tj. wszystkie wartości $x_i$ są różne. W ostatnich dwóch podzadaniach na każdym słupie mogą znajdować się co najwyżej dwie lampy.
Aby oświetlić ulicę, niektóre lampy mogą być włączone. Aktywna lampa o indeksie $i$ ma jasność $s_i$. Świeci ona w taki sposób, że oświetla ciągły odcinek ulicy o długości $s_i$ metrów od słupa, na którym się znajduje. Każda aktywna lampa może być skierowana w lewo lub w prawo. Jeśli $i$-ta lampa jest skierowana w lewo, oświetla odcinek ulicy $[x_i - s_i, x_i]$, a jeśli w prawo, to $[x_i, x_i + s_i]$.
Wybierzmy niepusty zbiór lamp, które zostaną włączone, aby oświetlić fragment ulicy. Nazwiemy ten zbiór lamp ekonomicznym, jeśli możliwe jest skierowanie każdej wybranej lampy w lewo lub w prawo w taki sposób, aby spełnione były dwa warunki:
- oświetlone odcinki tworzą ciągły fragment ulicy;
- żaden odcinek o niezerowej długości nie jest oświetlony jednocześnie przez dwie lub więcej lamp.
Poniższy rysunek przedstawia ekonomiczne podzbiory dwóch lamp dla drugiego przykładu z treści oraz sposoby oświetlenia ciągłego fragmentu ulicy. Jasność każdej lampy jest zapisana nad nią.
Znajdź liczbę ekonomicznych podzbiorów lamp. Jako odpowiedź wypisz resztę tej wartości modulo $10^9 + 7$.
Wejście
Pierwszy wiersz zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 10^5$) — liczbę lamp. Następnie znajduje się opis lamp.
Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $x_i$ i $s_i$ — współrzędną słupa, na którym znajduje się $i$-ta lampa, oraz jej jasność ($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$).
Gwarantowane jest, że na tym samym słupie znajdują się co najwyżej dwie lampy, tj. dla każdego $v$ istnieje co najwyżej dwa indeksy $i$ takie, że $x_i = v$.
Wyjście
Wypisz pojedynczą liczbę całkowitą — resztę z dzielenia liczby sposobów wyboru ekonomicznego podzbioru lamp przez $10^9 + 7$.
Podzadania
Wprowadzamy zmienną $t$ — maksymalną liczbę lamp, które mogą mieć tę samą współrzędną $x_i$.
Jeśli $t = 1$, to $x_1 < x_2 < \dots < x_n$.
Jeśli $t = 2$, to $x_1 \le x_2 \le \dots \le x_n$, a jeśli $x_i = x_{i+1}$, to $x_{i-1} < x_i$ i $x_{i+1} < x_{i+2}$ (jeśli odpowiednie lampy istnieją).
| Podzadanie | Punkty | $t$ | $n$ | Dodatkowe ograniczenia | Wymagane podzadania |
|---|---|---|---|---|---|
| 1 | 10 | $t = 1$ | $n \le 10$ | ||
| 2 | 15 | $t = 1$ | Dla dowolnych dwóch różnych lamp $i, j$, $x_i - s_i \ne x_j$ i $x_i + s_i \ne x_j - s_j$ | ||
| 3 | 15 | $t = 1$ | Dla dowolnych dwóch różnych lamp $i, j$, $s_i \ne s_j$ | ||
| 4 | 15 | $t = 1$ | Dla dowolnych dwóch różnych lamp $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$ | Jeśli $x_i = x_{i+1}$, to $s_i \ne s_{i+1}$ | 1 – 6 | |
| 8 | 5 | $t = 2$ | Przykłady, 1 – 7 |
Przykład
Wejście 1
2 2 3 7 2
Wyjście 1
3
Wejście 2
3 1 1 3 1 4 2
Wyjście 2
6
Wejście 3
5 3 2 4 2 5 2 6 2 7 2
Wyjście 3
10
Wejście 4
4 3 2 7 4 7 4 8 2
Wyjście 4
8
Wejście 5
5 1 2 1 3 2 1 2 2 4 1
Wyjście 5
19
Uwagi
W pierwszym przykładzie wszystkie trzy niepuste podzbiory lamp są ekonomiczne.
W drugim przykładzie wszystkie podzbiory lamp są ekonomiczne, z wyjątkiem zbioru $\{1, 2, 3\}$.