/* hdu4913 Least common multiple http://acm.hdu.edu.cn/showproblem.php?pid=4913 离散化 线段树 统计逆序数思想 tips: 1、线段树中一定要到处都取模，否则wa。。。 2、lazy是乘积的形式出现，不是加和 */ #include <cstdio> #include <algorithm> #include <vector> using namespace std; const long long Nmax=100005LL; const long long mod=1000000007LL; long long ans; int n; vector<long long> v; struct Node { long long a; long long b; }; Node num[Nmax]; long long a[Nmax],b[Nmax],ab[Nmax]; bool cmp(Node a,Node b) { if(a.a==b.a) return a.b<b.b; return a.a<b.a; } int get_id(long long x) { return lower_bound(v.begin(),v.end(),x)-v.begin()+1; } struct Tree { int l; int r; long long sum; long long times; long long lazy; }tree[Nmax*4]; void build(int root,int l,int r) { tree[root].l=l; tree[root].r=r; tree[root].sum=tree[root].times=0LL; tree[root].lazy=1LL; if(l==r) return; int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); } void push_down(int root) { if(tree[root].l==tree[root].r) { tree[root].lazy=1LL; return; } if(tree[root].lazy!=1LL) { tree[root<<1].lazy=(tree[root<<1].lazy*tree[root].lazy)%mod; tree[root<<1|1].lazy=(tree[root<<1|1].lazy*tree[root].lazy)%mod; tree[root<<1].sum=(tree[root<<1].sum*tree[root].lazy)%mod; tree[root<<1|1].sum=(tree[root<<1|1].sum*tree[root].lazy)%mod; tree[root].lazy=1LL; } } void insert(int root,int l,int r,int data) { if(tree[root].l==l&&tree[root].r==r) { tree[root].times+=data; return; } push_down(root); int mid=(tree[root].l+tree[root].r)>>1; if(mid>=l) insert(root<<1,l,r,data); if(mid<r) insert(root<<1|1,l,r,data); tree[root].times=tree[root<<1].times+tree[root<<1|1].times; } void insert_sum(int root,int l,int r,int data) { if(tree[root].l>=l&&tree[root].r<=r) { tree[root].sum=(tree[root].sum+data)%mod; return; } push_down(root); int mid=(tree[root].l+tree[root].r)>>1; if(mid>=l) insert_sum(root<<1,l,r,data); if(mid<r) insert_sum(root<<1|1,l,r,data); tree[root].sum=(tree[root<<1].sum+tree[root<<1|1].sum)%mod; } long long query_sum(int root,int l,int r) { if(tree[root].l>=l&&tree[root].r<=r) { return tree[root].sum%mod; } push_down(root); int mid=(tree[root].l+tree[root].r)>>1; long long ans=0LL; if(mid>=l) ans=( ans+query_sum(root<<1,l,r) )%mod; if(mid<r) ans=( ans+query_sum(root<<1|1,l,r) )%mod; while(ans<0) ans+=mod; return ans; } long long query(int root,int l,int r) { if(tree[root].l>=l&&tree[root].r<=r) { return tree[root].times; } int mid=(tree[root].l+tree[root].r)>>1; long long ans=0LL; if(mid>=l) ans+=query(root<<1,l,r); if(mid<r) ans+=query(root<<1|1,l,r); return ans; } void init() { v.clear(); ans=0LL; build(1,1,n); } int qpow(long long base,long long n) { base=base%mod; long long ans=1LL; while(n>0) { if(n&1) ans=(ans*base)%mod; base=base*base%mod; n>>=1; } while(ans<0) ans+=mod; return ans; } void update(int root,int l,int r) { if(tree[root].l>=l && tree[root].r<=r) { tree[root].lazy=(tree[root].lazy*2LL)%mod; tree[root].sum=(tree[root].sum*2LL)%mod; return; } push_down(root); int mid=(tree[root].l+tree[root].r)>>1; if(mid>=l) update(root<<1,l,r); if(mid<r) update(root<<1|1,l,r); tree[root].sum=(tree[root<<1].sum+tree[root<<1|1].sum)%mod; } void watch(int root,int l,int r) { printf("tree[%d]: l:%d,r:%d,sum:%lld,times:%lld,lazy:%lld ",root,tree[root].l,tree[root].r,tree[root].sum,tree[root].times,tree[root].lazy); if(l==r) return; int mid=(l+r)>>1; watch(root<<1,1,mid); watch(root<<1|1,mid+1,r); } int main() { //freopen("hdu4913.in","r",stdin); while(scanf("%d",&n)==1) { init(); for(int i=1;i<=n;i++) { scanf("%lld%lld",&num[i].a,&num[i].b); v.push_back(num[i].b); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); sort(num+1,num+1+n,cmp); int m=v.size(); for(int i=1;i<=n;i++) { //printf("times[%d]: ",i); int b=get_id(num[i].b); //printf("b:%d ",b); //printf("before: "); //watch(1,1,n); //printf("after: "); //watch(1,1,n); //printf("end!!!!!!!!!!!!!!!!! "); insert(1,b,b,1); long long x=query(1,1,b); //printf("%lld:%lld ",query(1,1,b),query(1,b,b)); //printf("x:%lld ",x); x=qpow(2,x-1); //printf("x:%lld ",x); x= (x*qpow(3,num[i].b)) %mod; //printf("x:%lld ",x); ans=( ans+ qpow(2,num[i].a)*x )%mod; //printf("ans:%lld ",ans); //if(kkk==0) //if(b!=n) if(b!=n) ans=(ans+(qpow(2,num[i].a)* query_sum(1,b+1,n)) %mod)%mod; //printf("ans:%lld ",ans); if(b!=n) update(1,b+1,n); insert_sum(1,b,b,x); //watch(1,1,n); } while(ans<0) ans+=mod; //printf("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ "); printf("%lld ",ans); } return 0; }