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
#include <bits/stdc++.h>
using namespace std;
int i,j,k,n, L,P;
long long a,b,q,z;
vector<array<int,2>> h;
bool cc;
array<long long,32> qq;
array<vector<int>,500001> g;
vector<array<int,2>> r,rn;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	q=1e9;
	q+=7;
	cin  >> n;
	for(i=0;i<n;i++) {
		cin >> L >> P;
		h.push_back({L,P});
	}
	for(j=n-1;j>=0;j--) {
		rn={};
		L=h[j][0];
		P=h[j][1];
		for(auto x:r) {
			if(x[0]<L || x[0]>P)
				rn.push_back(x);
			else {
				cc=1;
				for(auto y:g[j])
					if(y==x[1]) {
						cc=0;
						break;
					}
				if(cc)
				g[j].push_back(x[1]);
			}
		}
		for(auto y:g[j]) {
			rn.push_back({L,y});
				rn.push_back({P,y});
		}
		rn.push_back({L,j});
		rn.push_back({P,j});
		r=rn;
		//cout << r.size() << '\n';
		//for(auto w:r)
		//	cout << w[0] << ' ' << w[1] << "AA\n";
					
	}
	a=0;
	b=1;
	for(i=0;i<n;i++) {
		z=g[i].size()+1;
		//cout << i << ' ' << z << '\n';
		a=(a*z+b)%q;
		b=(z*b)%q;
	}
	z=q-2;
	for (i=0;i<=30;i++){
		qq[i]=z%2;
		z/=2;
	}
	z=1;
	//cout << a << ' ' << b << '\n';
	for (j=0;j<=30;j++){
		if (qq[j]){
			z*=b;
			z%=q;
		}
			b=(b*b)%q;			
	}
	a*=z;
	a%=q;
	cout << a << '\n';
	
}