Problem Description

This problem is translated from PA 2020 Round 3 Miny.

$n$ mines were delivered to the military training ground in Bytau and buried along a straight line. Each mine is located at a different position and has its own explosion radius. When a mine is detonated, it automatically detonates all mines that have not yet exploded and are within its explosion radius. If the distance between mine $a$ and mine $b$ is not greater than mine $b$'s explosion radius, then we say that mine $a$ is within mine $b$'s explosion radius.

Sergeant Bytomir wants to conduct an experiment. He chooses an arbitrary subset of mines (possibly empty) and manually detonates all mines in this subset at the same time. The result of the experiment is a set of mines that have exploded—either because they were manually detonated, or because they were detonated by other exploding mines.

How many different experiment results are possible for Bytomir? Two experiment results are considered the same if the sets of exploded mines are the same. Since the answer can be large, output it modulo $10^9+7$.

Input Format

The first line contains an integer $n$, the number of mines.

The next $n$ lines each contain two integers $a_i, r_i$, representing the position and explosion radius of a mine. You may assume that $a_1<a_2<\cdots<a_n$.

Output Format

Output the number of possible experiment results modulo $10^9+7$.

4
0 2
2 0
3 2
7 4

7

Hint

Explanation of Sample 1

You can obtain $7$ different experiment results:

• $\{\}$ (the empty set): if you do not detonate any mine;
• $\{1,2\}$ (mines $1,2$): if we detonate only mine $1$;
• $\{1,2,3\}$: if we detonate mines $1$ and $3$;
• $\{1,2,3,4\}$: if we detonate mines $1$ and $4$;
• $\{2\}$: if we detonate only mine $2$;
• $\{2,3\}$: if we detonate only mine $3$;
• $\{2,3,4\}$: if we detonate only mine $4$.

Note that the same experiment result can be obtained in different ways—for example, if we detonate mines $1$ and $2$, we also get the result $\{1,2\}$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 3\times 10^5$, $0\le a_i,r_i\le 10^{18}$.

Translated by ChatGPT 5