/* hdu4913 Least common multiple http://acm.hdu.edu.cn/showproblem.php?pid=4913 离散化 线段树 统计逆序数思想 tips: 1、线段树中一定要到处都取模，否则wa。。。 2、lazy是乘积的形式出现，不是加和*/ #include#include #include 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; }