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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll MOD = 1000000007;

struct Struktura{
    int *Dis;
    ll *Val;
    int start, size;

    Struktura(int els){
        start=1;
        while(start<els)
            start*=2;
        size=2*start;

        Dis = new int[size];
        fill(Dis, Dis+size, 0);
        Val = new ll[size];
        fill(Val, Val+size, 0ll);
    }
    ~Struktura(){
        delete []Dis;
        delete []Val;
    }
    void _update_middle_val(int v){
        ll leftVal = (Dis[2*v]?0:Val[2*v]);
        ll rightVal = (Dis[2*v+1]?0:Val[2*v+1]);
        Val[v] = (Dis[v]?0:((leftVal+rightVal)%MOD));
    }

    void _add_dis(int a, int b, int val, int v, int rA, int rB){
        if(a<=rA && rB<=b){
            Dis[v]+=val;
            if(v<start)
                _update_middle_val(v);
        }
        else{
            int rM = (rA+rB)/2;
            if(a<=rM)
                _add_dis(a, b, val, 2*v, rA, rM);
            if(rM<b)
                _add_dis(a, b, val, 2*v+1, rM+1, rB);
            _update_middle_val(v);
        }
    }
    void disable(int a, int b){
        _add_dis(a, b, 1, 1, 0, start-1);
    }
    void enable(int a, int b){
        _add_dis(a, b, -1, 1, 0, start-1);
    }

    void set_value(int p, ll val){
        int v = p+start;
        Val[v] = val;

        while(v>1){
            v/=2;
            _update_middle_val(v);
        }
    }

    ll _get_sum(int a, int b, int v, int rA, int rB){
        if(Dis[v])
            return 0;
        if(a<=rA && rB<=b)
            return Val[v];
        int rM = (rA+rB)/2;
        ll sum=0;
        if(a<=rM)
            sum += _get_sum(a, b, 2*v, rA, rM);
        if(rM<b)
            sum += _get_sum(a, b, 2*v+1, rM+1, rB);
        return sum%MOD;
    }
    ll get_sum(int a, int b){
        return _get_sum(a, b, 1, 0, start-1);
    }
};




int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //wczytaj dane
    int n;
    cin >> n;
    vector<ll>Pos(n+2),Range(n+2);
    for(int i=2;i<=n+1;i++)
        cin >> Pos[i] >> Range[i];
    Pos[0]=Pos[1]=numeric_limits<ll>::min()+42;

    //policz naiwne zakresy wybuchu
    vector<int>Left(n+2),Right(n+2);
    for(int i=2;i<=n+1;i++){
        Left[i] = lower_bound(Pos.begin(), Pos.end(), Pos[i]-Range[i])-Pos.begin();
        Right[i] = upper_bound(Pos.begin(), Pos.end(), Pos[i]+Range[i])-Pos.begin()-1;
    }

    //dynamik
    Struktura S(n+2);
    vector<ll>dp(n+2);
    vector<vector<pii>>forwardDels(n+2);

    dp[0]=dp[1]=1;
    S.set_value(0, 1);
    S.set_value(1, 1);

    for(int i=2;i<=n+1;i++){
        //usuń stare disable
        for(pii dis : forwardDels[i])
            S.enable(dis.first, dis.second);
        
        //dodaj disable wsteczne
        if(Left[i]<i)
            S.disable(Left[i]-1, i-2);

        //dodaj disable do przodu
        if(Right[i]>i){
            S.disable(0, i-2);
            forwardDels[Right[i]].push_back({0, i-2});
        }

        dp[i] = S.get_sum(0, i-1);
        S.set_value(i, dp[i]);
    }

    cout << dp[n+1] << "\n";

    return 0;
}