沿着一条长街，有若干灯柱，上面安装了 $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\}$ 之外，所有子集都是经济的。