긴 거리를 따라 $n$개의 가로등이 설치된 가로등 기둥이 있습니다. 거리를 따라 좌표계를 도입합시다. $i$번째 가로등이 설치된 기둥은 좌표 $x_i$에 위치합니다. 이 문제의 첫 6개 서브태스크(85점)에서는 두 가로등이 같은 기둥에 설치되지 않습니다. 즉, 모든 $x_i$ 값이 서로 다릅니다. 마지막 두 서브태스크에서는 각 기둥에 최대 두 개의 가로등이 있을 수 있습니다.

거리를 밝히기 위해 일부 가로등을 켤 수 있습니다. 켜진 $i$번째 가로등은 밝기 $s_i$를 가집니다. 이 가로등은 자신이 위치한 기둥에서 $s_i$미터 길이의 연속적인 거리 구간을 밝힙니다. 각 켜진 가로등은 왼쪽 또는 오른쪽으로 방향을 정할 수 있습니다. $i$번째 가로등이 왼쪽을 향하면 구간 $[x_i - s_i, x_i]$를, 오른쪽을 향하면 $[x_i, x_i + s_i]$를 밝힙니다.

거리의 한 구간을 밝히기 위해 켤 가로등의 비어 있지 않은 집합을 선택합시다. 이 가로등 집합을 경제적(economical)이라고 부르기 위해서는, 각 선택된 가로등을 왼쪽 또는 오른쪽으로 적절히 방향을 정하여 다음 두 조건을 만족시킬 수 있어야 합니다:

• 밝혀진 구간들이 하나의 연속적인 거리 구간을 이룹니다.
• 길이가 0이 아닌 구간이 두 개 이상의 가로등에 의해 동시에 밝혀지지 않습니다.

아래 그림은 두 번째 예제에서 두 가로등의 경제적 부분집합과 연속적인 거리 구간을 밝히는 방법을 보여줍니다. 각 가로등 위에는 밝기가 적혀 있습니다.

경제적인 가로등 부분집합의 개수를 구하십시오. 답으로는 이 값을 $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$에 대해 $x_i = v$인 인덱스 $i$는 최대 두 개입니다.

출력

하나의 정수를 출력하십시오 — 경제적인 가로등 부분집합을 선택하는 방법의 수를 $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}$입니다 (해당하는 가로등이 존재하는 경우).

예제

입력 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\}$을 제외한 모든 가로등 부분집합이 경제적입니다.