Along a long street, there are lampposts on which $n$ lanterns are located. Let's introduce a coordinate system along the street. The post on which the $i$-th lantern is placed is located at the point with coordinate $x_i$. In the first six subtasks of this problem, worth 85 points, no two lanterns are attached to the same post, i.e., all values of $x_i$ are distinct. In the last two subtasks, there can be at most two lanterns on each post.
To illuminate the street, some lanterns can be turned on. An active lantern with index $i$ has brightness $s_i$. It shines in such a way that it illuminates a continuous segment of the street of length $s_i$ meters from the post on which it is located. Each active lantern can be turned either to the left or to the right. If the $i$-th lantern is directed to the left, it illuminates the segment of the street $[x_i - s_i, x_i]$, and if to the right, then $[x_i, x_i + s_i]$.
Let's choose a non-empty set of lanterns to be turned on to illuminate a section of the street. We will call this set of lanterns economical if it is possible to direct each chosen lantern to the left or to the right in such a way that two conditions are met:
- the illuminated segments form a continuous segment of the street;
- no segment of non-zero length is illuminated by two or more lanterns simultaneously.
The figure below shows the economical subsets of two lanterns for the second sample from the statement and the ways to illuminate a continuous segment of the street. The brightness of each lantern is written above it.
Find the number of economical subsets of lanterns. As the answer, output the remainder of this value modulo $10^9 + 7$.
Input
The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of lanterns. Then follows the description of the lanterns.
Each of the next $n$ lines contains two integers $x_i$ and $s_i$ — the coordinate of the post where the $i$-th lantern is located and its brightness ($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$).
It is guaranteed that at most two lanterns are located on the same post, i.e., for each $v$ there are at most two indices $i$ such that $x_i = v$.
Output
Output a single integer — the remainder of the division of the number of ways to choose an economical subset of lanterns by $10^9 + 7$.
Subtasks
We introduce a variable $t$ — the maximum number of lanterns that can have the same coordinate $x_i$.
If $t = 1$, then $x_1 < x_2 < \dots < x_n$.
If $t = 2$, then $x_1 \le x_2 \le \dots \le x_n$, and if $x_i = x_{i+1}$, then $x_{i-1} < x_i$ and $x_{i+1} < x_{i+2}$ (if the corresponding lanterns exist).
| Subtask | Points | $t$ | $n$ | Additional Constraints | Required Subtasks |
|---|---|---|---|---|---|
| 1 | 10 | $t = 1$ | $n \le 10$ | ||
| 2 | 15 | $t = 1$ | For any two distinct lanterns $i, j$, $x_i - s_i \ne x_j$ and $x_i + s_i \ne x_j - s_j$ | ||
| 3 | 15 | $t = 1$ | For any two distinct lanterns $i, j$, $s_i \ne s_j$ | ||
| 4 | 15 | $t = 1$ | For any two distinct lanterns $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$ | If $x_i = x_{i+1}$, then $s_i \ne s_{i+1}$ | 1 – 6 | |
| 8 | 5 | $t = 2$ | Examples, 1 – 7 |
Examples
Input 1
2 2 3 7 2
Output 1
3
Input 2
3 1 1 3 1 4 2
Output 2
6
Input 3
5 3 2 4 2 5 2 6 2 7 2
Output 3
10
Input 4
4 3 2 7 4 7 4 8 2
Output 4
8
Input 5
5 1 2 1 3 2 1 2 2 4 1
Output 5
19
Note
In the first example, all three non-empty subsets of lanterns are economical.
In the second example, all subsets of lanterns are economical, except for the set $\{1, 2, 3\}$.