题目描述

一条长街上竖立着一些灯柱，上面安装着 $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]$。

我们选择一个非空的路灯集合来照亮一段街道。如果能够将集合中的每盏路灯选择向左或向右照射，使得以下两个条件同时成立，则称该集合是经济的：

• 被照亮的区间拼接成一段连续不断的街道区间；
• 任意长度非零的区间不会被两盏或以上的路灯同时照亮。

下图展示了样例 2 中包含两盏路灯的经济子集及其照亮连续区间的方案。每盏路灯上方标注了其亮度。

:::align{center} :::

请求出路灯的经济子集个数。输出答案对 $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 \ldots \le x_n$）。

保证同一灯柱上至多安装两盏路灯，即对任意坐标 $v$，满足 $x_i = v$ 的 $i$ 不超过两个。

输出格式

输出一个整数——路灯的经济子集个数对 $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

提示

说明

在第一个样例中，所有三个非空路灯子集都是合法的。

在第二个样例中，除了集合 $\{1, 2, 3\}$ 以外，其余所有子集都是合法的。

子任务

引入变量 $t$，表示可能位于同一坐标 $x_i$ 的路灯的最大数量。

若 $t = 1$，则 $x_1 < x_2 < \ldots < x_n$。

若 $t = 2$，则 $x_1 \le x_2 \le \ldots \le x_n$，且若 $x_i = x_{i+1}$，那么 $x_{i-1} < x_i$ 且 $x_{i+1} < x_{i+2}$（在对应下标存在的情况下）。

翻译由 DeepSeek V4 Pro 完成