dhy4 T3

/*大致思路：
首先按ai值排序，给每个点分配一个 rank
然后按bi值从小到大处理每个点
对于每个点,计算它对答案的贡献：
贡献值=已插入的、rank比它高的点的贡献和乘以3^b_i(当前最大的bi)，同时考虑它自己的选择情况(选/不选) 2^x

使用 线段树 高效维护和查询点的数量和贡献值

[1,n] ai_max bi_max  2^ai*3^bi  2^ai_max  3^bi_max

时间复杂度 O(n log n)
*/


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int n;
struct node{
	int x,y,rank;
}a[N];
bool cmp1(node x,node y){
	return x.x<y.x; 
}
bool cmp2(node x,node y){
	return x.y<y.y;
}
int sum[4*N],cnt[N*4],lazytag[4*N];
//sum为区间内所有点的贡献之和  cnt为区间内点的数量
//lazytag表示区间内点的贡献需要乘以2的ai次方 
void pushup(int u){
	sum[u]=(sum[u*2]+sum[u*2+1])%mod;
	cnt[u]=(cnt[u*2]+cnt[u*2+1])%mod;
	//合并贡献和点的个数 
}
long long qpow(long long a,long long p){
	long long res=1;
	while(p){
		if(p%2) res=(res*a)%mod;
		a=(a*a)%mod;
		p/=2;
	}
	return res;
} //快速幂 
void pushdown(int u){
	if(lazytag[u]){
		sum[u*2]=(sum[u*2]*qpow(2,lazytag[u]))%mod;
		sum[u*2+1]=(sum[u*2+1]*qpow(2,lazytag[u]))%mod;
		lazytag[u*2]+=lazytag[u];
		lazytag[u*2+1]+=lazytag[u];
		lazytag[u]=0;
	}
	//pushdown只涉及sum 
}
//基础操作
 
//**********************************************************************************************************************************************************

void update_cnt(int u,int l,int r,int pos,int y,int z){  //tmp->y
	if (l==r)
	{
	cnt[u]=1; //
	sum[u]=(qpow(2,y)*qpow(2,z))%mod;
//在当前数字x和前面区间tmp个rank值比x.rank小的中任意形成的子集，这个子集中x的rank为最大值，也就是说x.ai为这个子集中ai的最大值，那么x的初始贡献就是这些子集中的贡献 
//初计算初始贡献：2^y表示已插入的y个点的选择情况(每个点可选可不选) 2^z表示当前点的x值对贡献的影响
	return;
	}
	pushdown(u);//确保是先成的2，而不是加上更新的点再成的
	int mid=(l+r)>>1;
	if(pos<=mid) update_cnt(u*2,l,mid,pos,y,z);
	else update_cnt(u*2+1,mid+1,r,pos,y,z);
	pushup(u);//基本操作
}//目的是更新当前排名有个数

void update_sum(int u,int l,int r,int x,int y){
	if(l>=x&&r<=y){
	lazytag[u]++; //标记+1，表示贡献值需要乘以2
	sum[u]=(sum[u]*2)%mod; //更新
	return;}
	pushdown(u);
	int mid=(l+r)>>1;
	if(x<=mid)
	update_sum(u*2,l,mid,x,y);
	if(y>mid)
	update_sum(u*2+1,mid+1,r,x,y);
	pushup(u);//更新rank后面的区间
} 
long long query_cnt(int u,int l,int r,int x,int y) {
	if(l>=x&&r<=y){
		return cnt[u]; 
	}
	int mid=(l+r)>>1;
	pushdown(u);
	long long ans=0;
	if(x<=mid) ans+=query_cnt(u*2,l,mid,x,y);
	if(y>mid) ans+=query_cnt(u*2+1,mid+1,r,x,y);
	return ans;
}
long long query_sum(int u,int l,int r,int x,int y) {
	if (l>=x&&r<=y){
		return sum[u];
	}
	int mid=(l+r)>>1;
	long long ans=0;
	pushdown(u);
	if(x<=mid)
	ans=(ans+query_sum(u*2,l,mid,x,y))%mod;
	if(y>mid)
	ans=(ans+query_sum(u*2+1,mid+1,r,x,y))%mod;
	return ans%mod;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp1);//按ai排序 
	for(int i=1;i<=n;i++)
	a[i].rank=i;
	//rank ai 
	sort(a+1,a+1+n,cmp2); //按bi排序
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		int tmp=query_cnt(1,1,n,1,a[i].rank);
		//这是为了计算已经插入的、rank比当前点低的点的数量
		update_cnt(1,1,n,a[i].rank,tmp,a[i].x);
		//向线段树中插入一个新点,设置该点的初始贡献值,更新该位置的点计数
		ans=(ans+(query_sum(1,1,n,a[i].rank,n)*qpow(3,a[i].y))%mod)%mod;
		//计算当前点对答案的贡献并加入总答案
		if(a[i].rank!=n) update_sum(1,1,n,a[i].rank+1,n);
		//插入一个新点后，所有排名比它高的点的贡献值都需要翻倍（因为它们现在多了一个可以选择或不选择的点）
	}
	cout<<ans;
	
	
	return 0;
}