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
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

ll P(ll x,ll p) {ll res=1;for(;p;p>>=1) {if(p&1) res=res*x%mod; x=x*x%mod;} return res;}

const int N=500007,L=19;

int l[N],r[N];

int le[N],re[N];
int ls[N][L],rs[N][L];

ll ans[N];
int t[N];

int lca(int a,int b)
{
	if(min(a,b)==0) return 0;
	if(r[a]>=l[b]) return min(a,b);
	int B=b,A=a;
	for(int j=L-1;j>=0;j--)
	{
		if(ls[B][j]==0) continue;
		if(l[a]<l[ls[B][j]]) B=ls[B][j];
	}
	if(ls[B][0]==a) return a;
	for(int j=L-1;j>=0;j--)
	{
		if(rs[A][j]==0) continue;
		if(r[rs[A][j]]<r[b]) A=rs[A][j];
	}
	if(rs[A][0]==b) return b;
	int xd=0;
	for(int j=L-1;j>=0;j--)
	{
		if(rs[a][j]==0) continue;
		int t=rs[a][j];
		B=b;
		for(int k=L-1;k>=0;k--)
		{
			if(ls[B][k]==0) continue;
			if(ls[B][k]>=t) B=ls[B][k];
		}
		if(B==t) xd=max(xd,t);
		if(r[t]<l[B]) a=t;
	}
	return xd;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    set<pair<int,int>>S;
    S.insert({inf,0});
    for(int i=n;i>0;i--)
    {
		while(true)
		{
			pair<int,int>p=*S.lower_bound({l[i],0});
			if(p.st>r[i]) break;
			S.erase(p);
			if(p.nd>0) le[p.nd]=i;
			else re[-p.nd]=i;
		}
		S.insert({l[i],i});
		S.insert({r[i],-i});
	}
	for(int i=1;i<=n;i++)
	{
		ls[i][0]=le[i];
		rs[i][0]=re[i];
		for(int j=1;j<L;j++)
		{
			ls[i][j]=ls[ls[i][j-1]][j-1];
			rs[i][j]=rs[rs[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=n;i++) 
	{
		t[i]=lca(le[i],re[i]);
		ans[i]=1;
	}
	ll res=0;
	for(int i=n;i>0;i--)
	{
		ans[ls[i][0]]+=ans[i];
		ans[rs[i][0]]+=ans[i];
		ans[t[i]]-=ans[i];
		res=(res+P(ans[i],mod-2))%mod;
	}
	cout<<res<<endl;

    return 0;
}