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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef pair<ull, ull> PUU;
const ull MOD = 1e9 + 7;
const ull MAX_POS = 1e18;
#define PB push_back
#define NB 300001
int n;
const int pot = (1<<19);
vector<int> LS[2*pot], LSt[2*pot];
bitset<2*pot> visited;
int component[2*pot];
vector<bool> is_good;

ull add(ull a, ull b) {
	if(a + b < max(a, b) || a + b > MAX_POS) {
		return MAX_POS;
	}
	return a + b;
}
ull sub(ull a, ull b) {
	if(b >= a) {
		return 0;
	}
	return a - b;
}
struct mina {
	ull centre, left, right;
	mina() {centre = left = right = 0;}
	mina(const ull &c, const ull &l, const ull &r): centre(c), left(l), right(r){}
	void print() {
		cout<<centre<<" "<<left<<" "<<right<<"\n";
	}
};
vector<mina> vec;
set<pair<ull, int>> positions;
void prepare_tree() {
	for(int i = 1; i < pot; ++i) {
		LS[i].PB(2*i);
		LS[i].PB(2*i + 1);
		LSt[2*i].PB(i);
		LSt[2*i + 1].PB(i);
	}
}

void add_conection(int ver, int l_q, int r_q, int l_max, int r_max, int node) {
	if(r_q < l_max || r_max < l_q) {
		return;
	}
	else if(l_q == l_max && r_q == r_max) {
		//cout<<l_q<<" "<<r_q<<"\n";
		//cout<<ver<<" "<<node<<"\n";
		LS[ver].PB(node);
		LSt[node].PB(ver);
		return;
	}
	int mid = (l_max + r_max) / 2;
	add_conection(ver, l_q, min(r_q, mid), l_max, mid, 2*node);
	add_conection(ver, max(l_q, mid + 1), r_q, mid+1, r_max, 2*node + 1);
}

stack<int> reversed_order;
void dfs1(int i) {
	if(visited[i]) return;
	visited[i] = 1;
	for(auto x : LS[i]) {
		dfs1(x);
	}
	//cout<<"DODAJE: "<<i<<"\n";
	reversed_order.push(i);
}
vector<int> scc_graph[2*pot];
int cmp_cnt = 0;
//numeruj components
void dfs2(int i) {
	if(visited[i]) return;
	component[i] = cmp_cnt;
	visited[i] = 1;
	for(auto x : LSt[i]) {
		if(visited[x]) {
			if(cmp_cnt != component[x]) {
					scc_graph[component[x]].PB(cmp_cnt);
			} 
		}
		dfs2(x);
	}
}

void get_scc() {
	visited.reset();
	for(int i = 1; i < 2*pot; ++i) dfs1(i);
	visited.reset();
	while(!reversed_order.empty()) {
		//cout<<"przerabiam "<<reversed_order.top() - pot<<"\n";
		//if(reversed_order.top() < pot + n && reversed_order.top() >= pot) cout<<"przerabiam: "<<reversed_order.top()- pot<<"\n";
		dfs2(reversed_order.top()); 
		reversed_order.pop();
		++cmp_cnt;
	}
}
int compressed_count = 0;
vector<int> compressed[NB];
map<int, int> m;
vector<ull> wyjebane;
vector<ull> niewyjebane;

stack<int> toposorted;

void dfs3(int i) {
	if(visited[i]) return;
	visited[i] = 1;
	for(auto x : compressed[i]) {
		dfs3(x);
	}
	toposorted.push(i);
}

void toposort() {
	visited.reset();
	for(int i = 0; i < compressed_count; ++i) {
		dfs3(i);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	ull pos, rad;
	for(int i = 0; i < n; ++i) {
		cin>>pos>>rad;
		vec.PB(mina(pos, sub(pos, rad), add(pos,rad)));
		positions.insert({pos, i});
	}
	prepare_tree();//miny numerowane od zera
	for(int i = 0; i < n; ++i) {
		auto lewy_koniec = positions.lower_bound({vec[i].left, 0});
		auto prawy_koniec = positions.upper_bound({vec[i].right, n+3});
		prawy_koniec--;
		int lewosc = lewy_koniec->second;
		int prawosc = prawy_koniec->second;
		add_conection(pot + i, lewosc, prawosc, 0, pot-1, 1);
	}
	get_scc();
	is_good = vector<bool>(2*pot, 0);
	//cout<<cmp_cnt<<"\n";
	//JAK WYMYSLISZ ALGOSA TO PRZEFILTRUJ KRAWEDZIE I WIERZCHOLKI NAJLEPIEJ MAPA
	for(int i = 0; i < n; ++i) {
		if(m.find(component[i + pot]) == m.end()) {
			m[component[i+pot]] = compressed_count;
			compressed_count++;
		}
		is_good[component[i + pot]] = true;
		//cout<<"WIERZCHOLEK: "<<i<<" COMPONENT: "<<component[i+pot]<<"\n";
	}
	for(int i = 0; i < cmp_cnt; ++i) {
		if(is_good[i]) {
			int this_c = m[i];
			for(auto t : scc_graph[i]) {
				if(is_good[t]) {
					compressed[this_c].PB(m[t]);
				}
			}
		}
	}
	for(int i = 0; i < compressed_count; ++i) {
		auto it  = unique(compressed[i].begin(), compressed[i].end());
		compressed[i].resize(distance(compressed[i].begin(), it));
	}
	wyjebane = niewyjebane = vector<ull>(compressed_count, 1);
	toposort();
	ull zlicz=1;
	while(!toposorted.empty()) {
		int this_vertex = toposorted.top();
		toposorted.pop();
		ull this_all = (wyjebane[this_vertex] + niewyjebane[this_vertex])%MOD;
		if(compressed[this_vertex].size() == 0) {//JESTEM LISCIEM
			zlicz *= this_all;
			zlicz %= MOD;
		}
		else {//NIE JESTEM LISCIEM
			for(auto dziecko : compressed[this_vertex]) {
				wyjebane[dziecko] *= this_all;
				wyjebane[dziecko] %= MOD;
				niewyjebane[dziecko] *= niewyjebane[this_vertex];
				niewyjebane[dziecko] %= MOD;
			}
		}
	}
	cout<<zlicz<<"\n";
	return 0;
}