長い通りに沿って、$n$ 個のランタンが設置された街灯柱がある。通りに沿って座標系を導入する。$i$ 番目のランタンが置かれている柱は、座標 $x_i$ の点にある。この問題の最初の6つの小課題（85点相当）では、同じ柱に2つ以上のランタンが取り付けられることはない。すなわち、すべての $x_i$ は互いに異なる。最後の2つの小課題では、各柱に最大2つのランタンが取り付けられる可能性がある。

通りを照らすために、いくつかのランタンを点灯させることができる。点灯した $i$ 番目のランタンは明るさ $s_i$ を持つ。このランタンは、自身が置かれている柱から $s_i$ メートルの長さの連続した通り区間を照らすように光る。各点灯ランタンは左向きか右向きのいずれかに向けることができる。$i$ 番目のランタンが左向きの場合、通り区間 $[x_i - s_i, x_i]$ を照らし、右向きの場合は $[x_i, x_i + s_i]$ を照らす。

点灯させるランタンの空でない集合を選び、通りの一部を照らすことにする。このランタンの集合が経済的であるとは、選ばれた各ランタンを左または右に向けることで、次の2つの条件を満たすようにできることを言う:

• 照らされる区間が通りの連続した一区間をなす。
• 長さが正のどの区間も、2つ以上のランタンによって同時に照らされない。

以下の図は、問題文の2番目のサンプルに対する2つのランタンからなる経済的な部分集合と、連続した通り区間を照らす方法を示している。各ランタンの明るさはその上に書かれている。

経済的なランタンの部分集合の個数を求めよ。答えはこの値を $10^9 + 7$ で割った余りを出力せよ。

入力

最初の行には整数 $n$ ($1 \le n \le 10^5$) が含まれる — ランタンの個数である。その後、ランタンの説明が続く。

続く $n$ 行のそれぞれには、2つの整数 $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$)。

同じ柱には最大2つのランタンしか置かれていないことが保証される。すなわち、各 $v$ に対して $x_i = v$ となる添え字 $i$ は高々2つである。

出力

経済的なランタンの部分集合の選び方の個数を $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

注記

最初の例では、3つの空でないランタンの部分集合すべてが経済的である。

2番目の例では、集合 $\{1, 2, 3\}$ を除くすべてのランタンの部分集合が経済的である。