Problem Description

There are $n$ bombs on a straight line. The coordinate of each bomb is $x_i$, and its explosion radius is $r_i$. When a bomb explodes, if the position $x_j$ of another bomb satisfies:
$|x_j-x_i| \le r_i$, then that bomb will also be detonated.

Now, please help compute: if we detonate bomb $i$ first, how many bombs will be detonated in total?

The answer should be taken modulo $10^9 + 7$.

Input Format

The first line contains an integer $n$, representing the number of bombs.
Lines $2 \sim n+1$ each contain two integers, representing $x_i$ and $r_i$. It is guaranteed that $x_i$ is strictly increasing.

Output Format

Output one integer, representing $\sum \limits_{i=1}^n i\times$ the number of bombs that bomb $i$ can detonate.

4
1 1
5 1
6 5
15 15

32

Hint

Constraints
For $20\%$ of the testdata: $n\leq 100$.

For $50\%$ of the testdata: $n\leq 1000$.

For $80\%$ of the testdata: $n\leq 100000$.

For $100\%$ of the testdata: $1\le n\leq 500000$, $-10^{18}\leq x_{i}\leq 10^{18}$, $0\leq r_{i}\leq 2\times 10^{18}$.

Translated by ChatGPT 5