Miny
시간 제한2초메모리 제한1024 MB
각 지뢰가 자신의 폭발 반경 안에 있는 아직 터지지 않은 지뢰를 연쇄 폭발시킬 때, 임의의 부분집합을 수동으로 터뜨려 얻을 수 있는 서로 다른 폭발 집합의 개수를 센다.
문제
Na poligon wojskowy w Bajtowie przywieziono n min lądowych, które ułożono w linii prostej. Każda mina jest położona w innym miejscu i ma swój promień rażenia. Po zdetonowaniu, mina automatycznie powoduje detonację tych wszystkich min w swoim zasięgu rażenia, które nie wybuchły jeszcze do tej pory. Mówimy, że mina a znajduje się w zasięgu rażenia miny b, jeśli odległość między nimi jest nie większa niż promień rażenia miny b.
Sierżant Bajtomir chce przeprowadzić eksperyment. Wybierze on dowolny podzbiór min (być może pusty) i rozkaże ręcznie zdetonować ten podzbiór min w tym samym momencie. Wynikiem eksperymentu jest zbiór min, które wybuchły – czy to w wyniku ręcznej detonacji, czy w wyniku wybuchu jakiejś innej miny.
Ile możliwych wyników eksperymentu może uzyskać Bajtomir? Dwa wyniki eksperymentu uznajemy za takie same, jeśli w ich wyniku wybuchły te same miny. Ponieważ wynik może być duży, wypisz jego resztę z dzielenia przez 109 + 7.
입력
Pierwszy wiersz wejścia zawiera liczbę naturalną n (1 ≤ n ≤ 300 000) oznaczającą liczbę min. Każdy z kolejnych n wierszy zawiera po dwie liczby naturalne ai oraz ri (0 ≤ ai ≤ 1018, 0 ≤ ri ≤ 1018) oznaczające odpowiednio pozycję i-tej miny na prostej oraz jej promień rażenia. Możesz założyć, że a1 < a2 < a3 < . . . < an.
출력
Podaj resztę z dzielenia przez 109 + 7 liczby różnych wyników eksperymentu, które może uzyskać Bajtomir po ręcznym zdetonowaniu wybranego przez siebie podzbioru min.
힌트
Wyjaśnienie przykładu: Można uzyskać 7 różnych wyników eksperymentu:
- wynik {} (zbiór pusty), jeśli nie zdetonujemy ręcznie żadnej miny;
- wynik {1, 2} (miny 1 i 2), jeśli zdetonujemy ręcznie tylko minę 1;
- wynik {1, 2, 3}, jeśli zdetonujemy ręcznie miny 1 i 3;
- wynik {1, 2, 3, 4}, jeśli zdetonujemy ręcznie miny 1 i 4;
- wynik {2}, jeśli zdetonujemy ręcznie tylko minę 2;
- wynik {2, 3}, jeśli zdetonujemy ręcznie tylko minę 3;
- wynik {2, 3, 4}, jeśli zdetonujemy ręcznie tylko minę 4.
Zwróć uwagę na to, że ten sam wynik eksperymentu można często uzyskać na kilka różnych sposobów – na przykład wynik {1, 2} uzyskamy również, gdy zdetonujemy ręcznie miny 1 i 2.