Вдоль длинной улицы стоят столбы, на которых расположены $n$ фонарей. Введём систему координат вдоль улицы. Столб, на котором находится $i$-й фонарь, расположен в точке с координатой $x_i$. В первых шести подзадачах этой задачи, оцениваемых в 85 баллов, никакие два фонаря не прикреплены к одному и тому же столбу, то есть все значения $x_i$ различны. В последних двух подзадачах на каждом столбе может быть не более двух фонарей.
Для освещения улицы некоторые фонари можно включить. Активный фонарь с индексом $i$ имеет яркость $s_i$. Он светит так, что освещает непрерывный отрезок улицы длиной $s_i$ метров от столба, на котором он находится. Каждый активный фонарь может быть направлен либо влево, либо вправо. Если $i$-й фонарь направлен влево, он освещает отрезок улицы $[x_i - s_i, x_i]$, а если вправо — $[x_i, x_i + s_i]$.
Выберем непустое множество фонарей, которые будут включены для освещения участка улицы. Будем называть это множество экономичным, если можно направить каждый выбранный фонарь влево или вправо так, чтобы выполнялись два условия:
- освещённые отрезки образуют непрерывный участок улицы;
- никакой отрезок ненулевой длины не освещается одновременно двумя или более фонарями.
На рисунке ниже показаны экономичные подмножества из двух фонарей для второго примера из условия и способы освещения непрерывного участка улицы. Яркость каждого фонаря указана над ним.
Найдите количество экономичных подмножеств фонарей. В качестве ответа выведите остаток этого значения по модулю $10^9 + 7$.
Входные данные
Первая строка содержит одно целое число $n$ ($1 \le n \le 10^5$) — количество фонарей. Далее следует описание фонарей.
Каждая из следующих $n$ строк содержит два целых числа $x_i$ и $s_i$ — координату столба, на котором находится $i$-й фонарь, и его яркость ($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$).
Гарантируется, что на одном столбе расположено не более двух фонарей, т.е. для каждого $v$ существует не более двух индексов $i$ таких, что $x_i = v$.
Выходные данные
Выведите одно целое число — остаток от деления количества способов выбрать экономичное подмножество фонарей на $10^9 + 7$.
Подзадачи
Введём переменную $t$ — максимальное количество фонарей, которые могут иметь одинаковую координату $x_i$.
Если $t = 1$, то $x_1 < x_2 < \dots < x_n$.
Если $t = 2$, то $x_1 \le x_2 \le \dots \le x_n$, и если $x_i = x_{i+1}$, то $x_{i-1} < x_i$ и $x_{i+1} < x_{i+2}$ (если соответствующие фонари существуют).
| Подзадача | Баллы | $t$ | $n$ | Дополнительные ограничения | Необходимые подзадачи |
|---|---|---|---|---|---|
| 1 | 10 | $t = 1$ | $n \le 10$ | ||
| 2 | 15 | $t = 1$ | Для любых двух различных фонарей $i, j$ выполняется $x_i - s_i \ne x_j$ и $x_i + s_i \ne x_j - s_j$ | ||
| 3 | 15 | $t = 1$ | Для любых двух различных фонарей $i, j$ выполняется $s_i \ne s_j$ | ||
| 4 | 15 | $t = 1$ | Для любых двух различных фонарей $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$ | Если $x_i = x_{i+1}$, то $s_i \ne s_{i+1}$ | 1 – 6 | |
| 8 | 5 | $t = 2$ | Примеры, 1 – 7 |
Примеры
Входные данные 1
2 2 3 7 2
Выходные данные 1
3
Входные данные 2
3 1 1 3 1 4 2
Выходные данные 2
6
Входные данные 3
5 3 2 4 2 5 2 6 2 7 2
Выходные данные 3
10
Входные данные 4
4 3 2 7 4 7 4 8 2
Выходные данные 4
8
Входные данные 5
5 1 2 1 3 2 1 2 2 4 1
Выходные данные 5
19
Примечание
В первом примере все три непустых подмножества фонарей являются экономичными.
Во втором примере все подмножества фонарей являются экономичными, кроме множества $\{1, 2, 3\}$.