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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define DBG 0

int Q = 1'000'000'007;

int mn(long long x, int y) {
	return x * y % Q;
}

int odw(int x) {
	int ret = 1;
	for(int n = Q-2; n; n /= 2) {
		if (n%2) ret = mn(ret, x);
		x = mn(x, x);
	}
	return ret;
}

int U = 3;

int cofnij(const vector<vector<int>>& s, int o, int x, int cel) {
	if (!cel) return 0;
	if (x <= cel) return x;
	for (int i = o; i >= 0; i--) {
	 	if (s[x][i] >= cel) 
			x = s[x][i];
	}
	return x;
}

int main() {
	int n;
	scanf("%d", &n);
	while((1<<U) < n+2) U++;
	vector<int> a(n+1), b(n+1), ss(n+1), w(n+1, 1), ols(n+1), ors(n+1);
	vector<vector<int>> ls(n+1, vector<int>(U)), rs(n+1, vector<int>(U));
	a[0] = -1; b[0] = n+n+1;
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &a[i], &b[i]);
	}
	set<pair<int, int>> s;
	for (int i = n; i >= 1; i--) {
		for (auto it = s.lower_bound(make_pair(a[i], 0)); it != s.end(); it = s.erase(it)) {
			if (it->first > b[i]) break;
			if (it->second % 2) rs[it->second / 2][0] = i;
			else ls[it->second / 2][0] = i;
		}
		s.insert(make_pair(a[i], i+i));
		s.insert(make_pair(b[i], i+i+1));
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j < U; j++) {
			ls[i][j] = ls[ls[i][j-1]][j-1];
			if (ls[i][j]) ols[i] = j;
			rs[i][j] = rs[rs[i][j-1]][j-1];
			if (rs[i][j]) ors[i] = j;
			if (DBG && ls[i][j]) printf("skok ls %d %d :: %d\n", i,j,ls[i][j]);
			if (DBG && rs[i][j]) printf("skok rs %d %d :: %d\n", i,j,rs[i][j]);
			
		}
		int x = ls[i][0], y = rs[i][0];
		y = cofnij(ls, ols[y], y, x);
		x = cofnij(rs, ors[x], x, y);
		if (b[x] > a[y]) {
			ss[i] = min(x, y);
			continue;
		}
		for (int j = ors[x]; j >= 0; j--) {
			int nx = rs[x][j];
			if (!nx) continue;
			int ny = cofnij(ls, ols[y], y, nx);
			//printf("   test %d %d\n", nx, ny);
			if (b[nx] < a[ny]) {
				x = nx;
				y = ny;
			}
		}
		x = rs[x][0];
		ss[i] = x;
		if (DBG) printf("%d :: l=%d r=%d  ss=%d\n", i, ls[i][0], rs[i][0], ss[i]);
	}
	int ret = 0;
	for (int i = n; i >= 1; i--) {
		if (DBG) printf("%d :: 1/%d  == %d\n",i,w[i],odw(w[i]));
		ret += odw(w[i]);
		ret %= Q;
		w[ls[i][0]] += w[i];
		w[rs[i][0]] += w[i];
		w[ss[i]] -= w[i];
	}
	printf("%d\n", ret);
	return 0;
}