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>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define gc getchar_unlocked
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
constexpr ll mod = 1000000007ll;

void wczytaj(int &a){
	int c = gc();
	while(c < '0' || c > '9') c = gc();
	for(a = 0; c >= '0' && c <= '9'; c = gc()) a = 10*a+c-'0';
}

ll pot(ll a, ll b = mod-2ll){
	ll ret = 1ll;
	for(; b; b>>=1, a=(a*a)%mod) if(b&1ll) ret = (ret*a)%mod;
	return ret;
}

void solve(){
	int n;
	wczytaj(n);
	vector<pii> wejscie(n+1);
	wejscie[0] = {0, 2*n+1};
	
	int loog = 1;
	while((1<<loog) <= n) ++loog;
	vector tab_lewo(loog+1, vector(n+1, 0));
	vector tab_prawo(loog+1, vector(n+1, 0));
	
	set<pii> secik = {{1,0}, {2*n+1,0}, {2*n+2,0}};
	auto podziel = [&](int poz){
		auto it = secik.lower_bound({poz, 0});
		if(it->fi != poz) secik.emplace(poz, prev(it)->se);
	};
	auto kolor = [&](int poz){
		return prev(secik.lower_bound({poz+1, 0}))->se;
	};
	FOR(i, 1, n){
		int a, b;
		wczytaj(a), wczytaj(b);
		wejscie[i] = {a, b};
		tab_lewo[0][i] = kolor(a);
		tab_prawo[0][i] = kolor(b);
		podziel(a), podziel(b+1);
		auto it = secik.lower_bound({a, 0});
		while(it->fi <= b) it = secik.erase(it);
		secik.emplace(a, i);
	}
	
	FOR(j, 1, loog) FOR(i, 1, n){
		tab_lewo[j][i] = tab_lewo[j-1][tab_lewo[j-1][i]];
		tab_prawo[j][i] = tab_prawo[j-1][tab_prawo[j-1][i]];
	}
	
	vector<int> osiagalne(n+1, 1);
	for(int i = n+1; --i;){
		int a = tab_lewo[0][i];
		int b = tab_prawo[0][i];
		osiagalne[a] += osiagalne[i];
		osiagalne[b] += osiagalne[i];
		if(wejscie[a].se > wejscie[b].fi){
			osiagalne[min(a, b)] -= osiagalne[i];
			continue;
		}
		auto czy_git = [&](int lewo){
			if(b < lewo) return wejscie[lewo].se < wejscie[i].se;
			int prawo = b;
			for(int j = loog+1; ~--j;) if(int t = tab_lewo[j][prawo]; t >= lewo) prawo = t;
			return wejscie[lewo].se < wejscie[prawo].fi;
		};
		int lewo = a;
		if(!czy_git(lewo)){
			osiagalne[lewo] -= osiagalne[i];
			continue;
		}
		for(int j = loog+1; ~--j;) if(int t = tab_prawo[j][lewo]; czy_git(t)) lewo = t;
		osiagalne[tab_prawo[0][lewo]] -= osiagalne[i];
	}
	
	ll wyn = 0ll;
	FOR(i, 1, n) wyn = (wyn+pot(osiagalne[i]))%mod;
	printf("%lld", wyn);
}

int main(){
	solve();
	return 0;
}