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
//泥の分際で私だけの大切を奪おうだなん
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=1e9+7;
int qp(int x,int y)
{
	int res=1;
	for(int t=x; y; y>>=1,t=1ll*t*t%p)
		if(y&1) res=1ll*res*t%p;
	return res;
}
int cnt,n=read(),m=n*2+1;
int ls[1<<25],rs[1<<25],val[1<<25];
int l[1<<19],r[1<<19];
int rtl[1<<19],rtr[1<<19];
int fal[1<<19],far[1<<19];
set<pair<int,int>> sl,sr;
void insert(int nl,int nr,int t,int x)
{
	while(1)
	{
		++val[x];
		if(nl==nr) return ;
		int mid=(nl+nr)>>1;
		if(t<=mid) (!ls[x])&&(ls[x]=++cnt),nr=mid,x=ls[x];
		else (!rs[x])&&(rs[x]=++cnt),nl=mid+1,x=rs[x];
	}
}
int merge(int x,int y)
{
	if(!val[x]) return y;
	if(!val[y]) return x;
	val[x]+=val[y],
	ls[x]=merge(ls[x],ls[y]),
	rs[x]=merge(rs[x],rs[y]); 
	return x;
}
int rt[1<<19],inv[1<<19];
void calc(int nl,int nr,int x,int y,int z)
{
	if(!val[x]||!val[y]) return ;
	if(nl==nr)
	{
		--val[x],--val[y],rt[nl]=z;
		return ;
	}
	int mid=(nl+nr)>>1;
	calc(nl,mid,ls[x],ls[y],z),
	calc(mid+1,nr,rs[x],rs[y],z),
	val[x]=val[ls[x]]+val[rs[x]],
	val[y]=val[ls[y]]+val[rs[y]];
	return ;
}
int vl[1<<19],vr[1<<19],all[1<<19];
vector<pair<int,int>> ql[1<<19],qr[1<<19];
int tr[1<<20];
void add(int x,int k){while(x<=m)tr[x]+=k,x+=x&(-x);}
int find(int x){int r=0;while(x)r+=tr[x],x-=x&(-x);return r;}
signed main()
{
	inv[1]=1,r[n+1]=m;
	for(int i=2; i<=n; ++i) inv[i]=1ll*(p-(p/i))*inv[p%i]%p;
	for(int i=1; i<=n; ++i) l[i]=read(),r[i]=read();
	for(int i=1; i<=n+1; ++i)
	{
		rtl[i]=++cnt,rtr[i]=++cnt;
		while(1)
		{
			auto it=sl.lower_bound({l[i],-1});
			if(it==sl.end()||it->first>r[i]) break;
			fal[it->second]=i,
			rtl[i]=merge(rtl[i],rtl[it->second]),sl.erase(it);
		}
		while(1)
		{
			auto it=sr.lower_bound({l[i],-1});
			if(it==sr.end()||it->first>r[i]) break;
			far[it->second]=i,
			rtr[i]=merge(rtr[i],rtr[it->second]),sr.erase(it);
		}
		calc(1,n+1,rtl[i],rtr[i],i),
		sl.insert({l[i],i}),sr.insert({r[i],i}),
		insert(1,n+1,i,rtl[i]),insert(1,n+1,i,rtr[i]);
	}
	for(int i=1; i<=n; ++i)
		ql[fal[i]-1].push_back({i,1}),
		ql[i].push_back({i,-1});
	for(int i=1; i<=n; ++i)
	{
		add(r[i],1);
		for(auto [x,y]:ql[i])
			vl[x]+=find(l[x])*y;
	}
	memset(tr,0,sizeof(tr));
	for(int i=1; i<=n; ++i)
		qr[far[i]-1].push_back({i,1}),
		qr[i].push_back({i,-1});
	for(int i=1; i<=n; ++i)
	{
		add(m+1-l[i],1);
		for(auto [x,y]:qr[i])
			vr[x]+=find(m+1-r[x])*y;
	}
	int ans=0;
	for(int i=n; i>=1; --i) vl[i]+=vl[fal[i]];
	for(int i=n; i>=1; --i) vr[i]+=vr[far[i]];
	for(int i=1; i<=n+1; ++i)
		all[i]=i+vl[i]+vr[i];
	for(int i=1; i<=n; ++i)
		ans=(ans+inv[all[rt[i]]-all[i]])%p;
	printf("%d\n",ans);
	return 0;
}