题目描述

沿着一条很长的街道立着若干灯柱，灯柱上共有 $n$ 盏灯。沿街建立一维坐标系，第 $i$ 盏灯所在灯柱的坐标为 $x_i$。

在本题前六个子任务中，任意两盏灯不在同一根灯柱上，也就是说所有 $x_i$ 互不相同。最后两个子任务中，每根灯柱上最多可以有两盏灯。

为了照亮街道，可以打开其中一些灯。若第 $i$ 盏灯被打开，它的亮度为 $s_i$，它能照亮从所在灯柱出发、长度为 $s_i$ 的一个连续街道区间。每盏打开的灯可以朝左或朝右照射：

• 若第 $i$ 盏灯朝左，它照亮区间 $[x_i-s_i,x_i]$；
• 若第 $i$ 盏灯朝右，它照亮区间 $[x_i,x_i+s_i]$。

选择一个非空灯集用于照明。若可以为这个灯集中的每盏灯选择朝左或朝右，使得同时满足以下两个条件，则称这个灯集是经济的：

1. 所有被照亮的区间合起来形成一个连续区间；
2. 没有任何长度非零的街道区间被两盏或更多灯同时照亮。

也就是说，选择的灯经过定向后应当恰好首尾相接地覆盖一个连续区间，不能出现空隙，也不能出现正长度重叠。

求经济灯集的数量。答案对 $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, \qquad 1\le s_i\le 5\cdot 10^5, \qquad x_1\le x_2\le\cdots\le x_n。$$

保证每个坐标上最多有两盏灯，即对于任意 $v$，满足 $x_i=v$ 的下标 $i$ 不超过两个。

输出格式

输出一个整数，表示经济灯集数量对 $10^9+7$ 取模的结果。

样例 1

2
2 3
7 2

3

样例 2

3
1 1
3 1
4 2

6

样例 3

5
3 2
4 2
5 2
6 2
7 2

10

样例 4

4
3 2
7 4
7 4
8 2

8

样例 5

5
1 2
1 3
2 1
2 2
4 1

19

样例说明

在第一个样例中，所有三个非空灯集都是经济的。

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

子任务与评分

令 $t$ 表示同一坐标上最多有多少盏灯。

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

若 $t=2$，则 $x_1\le x_2\le\cdots\le x_n$，且若 $x_i=x_{i+1}$，则在存在相应下标时有 $x_{i-1}<x_i$ 且 $x_{i+1}<x_{i+2}$。

子任务	分值	限制	必要子任务
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		$t=1$，对任意不同灯 $i,j$，$s_i\ne s_j$
4		$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