1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
long long n, pos[300007], rad[300007], res, mod = 1000000007;
long long l[300007], f[300007], r[300007];
long long first(long long x){
  long long p = 0, k = x;
  while(p < k){
    long long mid = (p + k) / 2;
    if(pos[mid] < pos[x] - rad[x])
      p = mid + 1;
    else
      k = mid;
  }
  return p;
}
long long tree[1 << 20], M = 1;
long long getMin(long long p, long long k){
  long long res = LLONG_MAX;
  p += M; k += M;
  while(p <= k && p > 0 && k > 0){
    if(p % 2 == 1) res = min(res, tree[p++]);
    if(k % 2 == 0) res = min(res, tree[k--]);
    p /= 2;
    k /= 2;
  }
  return res;
}
void wyznaczL(){
  for(long long i = 0;i < 2 * M;i++) tree[i] = LLONG_MAX;
  for(long long i = 0;i < n;i++){
    long long poc = first(i);
    l[i] = poc == i ? i : getMin(poc, i - 1);
    long long v = i + M;
    tree[v] = l[i];
    while(v > 1){
      v /= 2;
      tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
    }
  }
}
struct fbomb {
  long long i, zasieng_w_prawo, na_prawo;
  fbomb(long long _i, long long _zasieng_w_prawo, long long _na_prawo) {
    i = _i;
    zasieng_w_prawo = _zasieng_w_prawo;
    na_prawo = _na_prawo;
  }
};
void wyznaczF(){
  stack<fbomb> staszic;
  for(long long i = n;i > 0;i--){
    pos[i] = pos[i - 1];
    rad[i] = rad[i - 1];
  }
  staszic.push(fbomb(1, pos[1] + rad[1], pos[1]));
  for(long long i = 2;i <= n;i++){
    while(!staszic.empty() && staszic.top().zasieng_w_prawo < pos[i]) staszic.pop();
    if(!staszic.empty()){
      f[i] = staszic.top().i;
      if((pos[i] - rad[i]) <= staszic.top().na_prawo){
        staszic.top().i = i;
        staszic.top().zasieng_w_prawo = max(staszic.top().zasieng_w_prawo, pos[i] + rad[i]);
        staszic.top().na_prawo = pos[i];
      }
    }
    staszic.push(fbomb(i, pos[i] + rad[i], pos[i]));
  }
  for(long long i = 0;i < n;i++)
    f[i] = f[i + 1] - 1;
}
long long dp[2][300007];
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for(long long i = 0;i < n;i++){
    cin >> pos[i] >> rad[i];
  }

  while(M < n) M *= 2;
  wyznaczL();
  wyznaczF();

  dp[0][0] = 1; dp[1][0] = 1;
  for(long long i = 1;i < n;i++){
    if(l[i] == 0)
      dp[1][i] = 1;
    if(l[i] > 0)
      dp[1][i] = (dp[1][l[i] - 1] + dp[0][l[i] - 1]) % mod;
    dp[0][i] = (dp[0][i - 1] + dp[1][i - 1]) % mod;
    if(f[i] != -1)
      dp[0][i] = (mod + dp[0][i] - dp[1][f[i]]) % mod;
  }
  cout << (dp[0][n - 1] + dp[1][n - 1]) % mod;
}