Problem Description

On a long street, there are some lamp posts with $n$ streetlights installed. We set up a coordinate system along the street. The lamp post of the $i$-th streetlight is located at coordinate $x_i$. In the first six subtasks of this problem (worth 85 points in total), no two streetlights are installed on the same lamp post, i.e. all $x_i$ are distinct. In the last two subtasks, each lamp post can have at most two streetlights.

To light up the street, we can turn on some of the streetlights. If the $i$-th streetlight is turned on, it has brightness $s_i$. When it shines, starting from its lamp post, it can illuminate a continuous segment of the street with length $s_i$ meters. Each turned-on streetlight can be oriented either to the left or to the right. If the $i$-th streetlight shines to the left, it illuminates the interval $[x_i - s_i, x_i]$; if it shines to the right, it illuminates the interval $[x_i, x_i + s_i]$.

We choose a non-empty set of streetlights to illuminate a segment of the street. If it is possible to choose, for every streetlight in the set, whether it shines left or right so that the following two conditions hold at the same time, then the set is called economical:

• The illuminated intervals can be joined into one continuous street interval.
• No non-zero-length interval is illuminated by two or more streetlights at the same time.

The figure below shows an economical subset with two streetlights in Sample 2 and one way to illuminate a continuous interval. The brightness of each streetlight is labeled above it.

:::align{center} :::

Please compute the number of economical subsets of streetlights. Output the answer modulo $10^9 + 7$.

Input Format

The first line contains an integer $n$ ($1 \le n \le 10^5$), the number of streetlights. The next lines describe the streetlights.

Each of the next $n$ lines contains two integers $x_i$ and $s_i$, representing the coordinate of the lamp post of the $i$-th streetlight and its brightness, respectively ($1 \le x_i \le 5 \cdot 10^5$, $1 \le s_i \le 5 \cdot 10^5$, $x_1 \le x_2 \le \ldots \le x_n$).

It is guaranteed that at most two streetlights are installed on the same lamp post, i.e. for any coordinate $v$, the number of indices $i$ such that $x_i = v$ is at most two.

Output Format

Output one integer: the number of economical subsets of streetlights modulo $10^9 + 7$.

2
2 3
7 2

3

3
1 1
3 1
4 2

6

5
3 2
4 2
5 2
6 2
7 2

10

4
3 2
7 4
7 4
8 2

8

5
1 2
1 3
2 1
2 2
4 1

19

Hint

Notes

In the first sample, all three non-empty subsets of streetlights are valid.

In the second sample, all subsets are valid except the set $\{1, 2, 3\}$.

Subtasks

Introduce a variable $t$, which denotes the maximum number of streetlights that may be located at the same coordinate $x_i$.

If $t = 1$, then $x_1 < x_2 < \ldots < x_n$.

If $t = 2$, then $x_1 \le x_2 \le \ldots \le x_n$, and if $x_i = x_{i+1}$, then $x_{i-1} < x_i$ and $x_{i+1} < x_{i+2}$ (when the corresponding indices exist).

The translation was completed by DeepSeek V4 Pro.

Translated by ChatGPT 5