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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;	

struct splitmix64_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
 
template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;
 
template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> para;
const ll inf = 1e18 + 7;
const ll maxN = 1e6 + 5;
const int MAX = 5e3;
const ll MOD = 1e9 + 7;

int n;
ll dp[MAX][MAX];
ll pos[maxN], range[maxN];
ll sum[maxN];
vi ranges[maxN];
int has[maxN];

void generateRanges() {
	// TODO in n log n if DP fixed
	RI(i, n) {
		int lft = i - 1;
		ll leftRange = pos[i] - range[i];
		ll rightRange = pos[i] + range[i];
		int rgh = i + 1;
		while (true) {
			int prevLft = lft;
			int prevRgh = rgh;
			while(lft > 0 && leftRange <= pos[lft]) {
				leftRange = min(leftRange, pos[lft] - range[lft]);
				rightRange = max(rightRange, pos[lft] + range[lft]);
				lft--;	
			}
			while (rgh <= n && rightRange >= pos[rgh]) {
				rightRange = max(rightRange, pos[rgh] + range[rgh]);
				leftRange = min(leftRange, pos[rgh] - range[rgh]);
				rgh++;
			}
			if (rgh == prevRgh && lft == prevLft) break;
		}
		rgh--;
		lft++;
		ranges[rgh].pb(lft);
	}
}
// sprawdz MODULO!
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	RI(i, n) {
		cin >> pos[i] >> range[i];
	}
	generateRanges();
	sum[0] = 1;
	RI(i, n) {
		ranges[i].erase(unique(ranges[i].begin(), ranges[i].end()), ranges[i].end());
		sum[i] = sum[i - 1];
		if (ranges[i].empty()) continue;
		int cnt = 0;
		RI(j, ranges[i].back()) {
			if (ranges[i][cnt] == j) {
				has[j] = i;
				sum[i] = (sum[i] + sum[j - 1]) % MOD;
				cnt++;
			} else {
				if (has[j] >= ranges[i][cnt]) {
					has[j] = i;
					sum[i] = (sum[i] + sum[j - 1]) % MOD;
				}
			}
		}
	}
	cout << sum[n] << endl;
	return 0;
}