//#pragma GCC target("avx512f") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include #include #include #define fst first #define snd second #define len(a) (ll)size(a) #define ppc(a) (ll)__builtin_popcountll(a) #define sq(a) ((a)*(a)) #define bit(a) (1LL<<(a)) #define fin(...) exit(pr(__VA_ARGS__)) #define pb() pop_back() #define ep(...) emplace(__VA_ARGS__) #define eb(...) emplace_back(__VA_ARGS__) #define ef(...) emplace_front(__VA_ARGS__) #define ei(...) else if(__VA_ARGS__) #define el else #define wh(...) while(__VA_ARGS__) #define lb(...) lower_bound(__VA_ARGS__) #define ub(...) upper_bound(__VA_ARGS__) #define srt(...) sort(all(__VA_ARGS__)) #define rev(...) reverse(all(__VA_ARGS__)) #define uni(a) srt(a);a.erase(unique(all(a)),end(a)) #define join(a,b) copy(all(b),back_inserter(a)) #define ov3(a,b,c,d,...) d #define ov4(a,b,c,d,e,...) e #define ov5(a,b,c,d,e,f,...) f #define ov6(a,b,c,d,e,f,g,...) g #define bg begin #define rbg rbegin #define all1(v) bg(v),end(v) #define all2(v,b) bg(v),bg(v)+b #define all3(v,a,b) bg(v)+a,bg(v)+b #define all(...) ov3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__) #define rll1(v) rbg(v),rend(v) #define rll2(v,b) rbg(v),rbg(v)+b #define rll3(v,a,b) rbg(v)+a,rbg(v)+b #define rll(...) ov3(__VA_ARGS__,rll3,rll2,rll1)(__VA_ARGS__) #define rep1(b) for(ll ii=0;ii<(ll)(b);ii++) #define rep2(i,b) for(ll i=0;i<(ll)(b);i++) #define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c)) #define rep(...) ov4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define per1(a) rep(a) #define per2(i,a) for(ll i=(ll)(a)-1;i>=0;i--) #define per3(i,a,b) for(ll i=(ll)(a)-1;i>=(ll)(b);i--) #define per4(i,a,b,c) for(ll i=(ll)(a)-1;i>=(ll)(b);i-=(ll)(c)) #define per(...) ov4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__) #define foe1(a) rep(len(a)) #define foe2(a,v) for(au&&a:v) #define foe3(a,b,v) for(au&&[a,b]:v) #define foe4(a,b,c,v) for(au&&[a,b,c]:v) #define foe5(a,b,c,d,v) for(au&&[a,b,c,d]:v) #define foe(...) ov5(__VA_ARGS__,foe5,foe4,foe3,foe2,foe1)(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;lin(__VA_ARGS__) #define ST(...) str __VA_ARGS__;lin(__VA_ARGS__) #define UL2(n,a) u1 a(n);lin(a) #define UL3(n,a,b) u1 a(n),b(n);lin(a,b) #define UL4(n,a,b,c) u1 a(n),b(n),c(n);lin(a,b,c) #define UL5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);lin(a,b,c,d) #define UL6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);lin(a,b,c,d,e) #define UL(...) ov6(__VA_ARGS__,UL6,UL5,UL4,UL3,UL2)(__VA_ARGS__) #define UV2(n,a) u1 a(n);vin(a) #define UV3(n,a,b) u1 a(n),b(n);vin(a,b) #define UV4(n,a,b,c) u1 a(n),b(n),c(n);vin(a,b,c) #define UV5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);vin(a,b,c,d) #define UV6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);vin(a,b,c,d,e) #define UV(...) ov6(__VA_ARGS__,UV6,UV5,UV4,UV3,UV2)(__VA_ARGS__) #define DL2(n,a) v1a(n);lin(a) #define DL3(n,a,b) v1a(n),b(n);lin(a,b) #define DL4(n,a,b,c) v1a(n),b(n),c(n);lin(a,b,c) #define DL5(n,a,b,c,d) v1a(n),b(n),c(n),d(n);lin(a,b,c,d) #define DL(...) ov5(__VA_ARGS__,DL5,DL4,DL3,DL2)(__VA_ARGS__) #define DV2(n,a) v1a(n);vin(a) #define DV3(n,a,b) v1a(n),b(n);vin(a,b) #define DV4(n,a,b,c) v1a(n),b(n),c(n);vin(a,b,c) #define DV5(n,a,b,c,d) v1a(n),b(n),c(n),d(n);vin(a,b,c,d) #define DV(...) ov5(__VA_ARGS__,DV5,DV4,DV3,DV2)(__VA_ARGS__) #define I template #define J class #define oo operator #define rr return #define ss struct #define uu using #define as assert #define au auto #define bk break #define bo bool #define cs const #define ct continue #define endl "\n" #define vo void #define fn function uu namespace atcoder; uu namespace std; uu namespace boost::multiprecision; uu ll=long long; uu ld=long double; uu str=string; Iuu v1=vector; Iuu v2=v1>; Iuu v3=v1>; Iuu v4=v1>; Iuu mset=multiset; uu u1=v1; uu u2=v1; uu u3=v1; uu u4=v1; uu pl=pair; uu ql=queue; uu sl=set; uu msl=mset; uu ml=map; uu mnt=modint1000000007; uu is=istream; uu os=ostream; ll inf=3e18; ld pi=acosl(-1); ld ee=1e-10; str sp=" "; str nc=""; str nl="\n"; str first(bo t=1){rr t?"first":"second";} str First(bo t=1){rr t?"First":"Second";} str yes(bo t=1){rr t?"yes":"no";} str Yes(bo t=1){rr t?"Yes":"No";} str YES(bo t=1){rr t?"YES":"NO";} str no(){rr "no";} str No(){rr "No";} str NO(){rr "NO";} str possible(bo t=1){rr t?"possible":"impossible";} str Possible(bo t=1){rr t?"Possible":"Impossible";} str POSSIBLE(bo t=1){rr t?"POSSIBLE":"IMPOSSIBLE";} Iuu heap_max=std::priority_queue; Iuu heap_min=std::priority_queue,greater>; ll at(ll S,ll i){rr S>>i&1;} IT at(cs v1&v,ll i){ll n=len(v);rr v[(i%n+n)%n];} Ill sig(cs T&a){rr(a>ee)-(a<-ee);} Ill sig(cs T&a,cs T&b){rr sig(a-b);} Iv1&oo++(v1&v){foe(x,v)x++;rr v;} Iv1&oo--(v1&v){foe(x,v)x--;rr v;} Iv1oo++(v1&v,int){au r=v;++v;rr r;} Iv1oo--(v1&v,int){au r=v;--v;rr r;} Iv1&oo+=(v1&v,cs U&a){foe(x,v)x+=a;rr v;} Iv1&oo-=(v1&v,cs U&a){foe(x,v)x-=a;rr v;} Iv1&oo*=(v1&v,cs U&a){foe(x,v)x*=a;rr v;} Iv1&oo/=(v1&v,cs U&a){foe(x,v)x/=a;rr v;} Iv1&oo+=(v1&v,cs v1&u){rep(i,len(v))v[i]+=u[i];rr v;} Iv1&oo-=(v1&v,cs v1&u){rep(i,len(v))v[i]-=u[i];rr v;} Iv1&oo*=(v1&v,cs v1&u){rep(i,len(v))v[i]*=u[i];rr v;} Iv1&oo/=(v1&v,cs v1&u){rep(i,len(v))v[i]/=u[i];rr v;} Ibo amax(T&a,cs U&b){rr abo amin(T&a,cs U&b){rr a>b?a=b,1:0;} IT max(cs v1&a){rr *max_element(all(a));} IT min(cs v1&a){rr *min_element(all(a));} Ill argmax(cs v1&a){rr max_element(all(a))-bg(a);} Ill argmin(cs v1&a){rr min_element(all(a))-bg(a);} Iau max(T...a){rr max(initializer_list>{a...});} Iau min(T...a){rr min(initializer_list>{a...});} IT gcd(cs T&a,cs A&...b){rr gcd(a,gcd(b...));} IT sum(cs v1&a){rr aJumulate(all(a),T(0));} Ill lbs(cs v1&a,cs T&b){rr lb(all(a),b)-bg(a);} Ill ubs(cs v1&a,cs T&b){rr ub(all(a),b)-bg(a);} Iau mm(cs T&a,cs T&b){rr pair(min(a,b),max(a,b));} Iau mm(cs pair&p){rr mm(p.fst,p.snd);} u1 iota(ll n,ll a=0){u1 i(n);iota(all(i),a);rr i;} vo emplace_front(u1&v,ll x=0){v.ep(bg(v),x);} Iau vmap(cs fn&f,v1x){v1y;foe(a,x)y.eb(f(a));rr y;} Iau keys(cs map&m){v1r;foe(k,_,m)r.eb(k);rr r;} Iau vals(cs map&m){v1r;foe(_,v,m)r.eb(v);rr r;} ss _{_(){cin.tie(0);ios::sync_with_stdio(0);cout<>(is&i,mnt&x){ll t;i>>t;x=t;rr i;} os&oo<<(os&o,cs mnt&x){rr o<is&oo>>(is&i,pair&p){rr i>>p.fst>>p.snd;} Ios&oo<<(os&o,cs pair&p){rr o<is&oo>>(is&i,v1&v){foe(x,v)i>>x;rr i;} Ios&oo<<(os&o,cs v1&v){foe(x,v)o<os&oo<<(os&o,cs v2&v){foe(x,v)o<os&oo<<(os&o,cs set&s){foe(x,s)o<os&oo<<(os&o,cs mset&s){foe(x,s)o<os&oo<<(os&o,cs map&m){foe(p,m)o<os&oo<<(os&o,queueq){wh(len(q))o<os&oo<<(os&o,dequeq){wh(len(q))o<os&oo<<(os&o,heap_maxq){wh(len(q))o<os&oo<<(os&o,heap_minq){wh(len(q))o<ll pr(cs T&a,cs A&...b){cout<ll db(cs T&a,cs A&...b){cerr<vo lin(T&...a){(cin>>...>>a);} Ivo vin(ll i,T&...a){(cin>>...>>a[i]);} Ivo vin(v1&a,A&...b){rep(i,len(a))vin(i,a,b...);} Ivo rs(v1&v,ll n){v.resize(n);} Ivo rs(v1&V,ll n,cs A&...a){rs(V,n);foe(v,V)rs(v,a...);} Ivo fl(T&x,cs U&a){x=a;} Ivo fl(v1&V,cs U&a){foe(v,V)fl(v,a);} vo zi(cs u1&v,u1&h){foe(x,h)x=lbs(v,x);} Ivo zi(cs u1&v,u1&h,T&...t){zi(v,h);zi(v,t...);} Iu1 zip(T&...a){u1 v;foe(e,{a...})join(v,e);uni(v);zi(v,a...);rr v;} Ivo vs(cs u1&o,v1&a){au c=a;rep(i,len(a))a[i]=c[o[i]];} Ivo vs(cs u1&o,v1&a,A&...b){vs(o,a);vs(o,b...);} Iau vsrt(cs fn&f,T&...a){ ll n=0;foe(e,{a...})n=len(e); u1 o=iota(n),p(n); sort(all(o),f); rep(i,n)p[o[i]]=i; vs(o,a...); rr pair(o,p); } IT bs(cs fn&j,T o,T n){ T d=(T)ee?ee:1; wh(abs(o-n)>d)(j((o+n)/2)?o:n)=(o+n)/2; rr o; } Iau zt(v1a){rep(i,1,len(a))a[i]+=a[i-1];rr a;} Iau mb(v1a){per(i,len(a),1)a[i]-=a[i-1];rr a;} Iau zt(v2a){foe(v,a)v=zt(v);rep(i,1,len(a))a[i]+=a[i-1];rr a;} Iau mb(v2a){foe(v,a)v=mb(v);per(i,len(a),1)a[i]-=a[i-1];rr a;} IT exq(ll n,T r,T x){wh(n){if(n&1)r*=x;x*=x;n/=2;}rr r;} u1 dvs(ll n){ml m;rep(i,1,n/i+1)if(n%i==0)m[i]++,m[n/i]++;rr keys(m);} ml fct(ll n){ml m;rep(i,2,n/i+1)wh(n%i==0)m[i]++,n/=i;if(n>1)m[n]++;rr m;} ll pom(ll x,ll n,ll m=inf){ll r=1;wh(n){if(n&1)r*=x,r%=m;x*=x,x%=m,n/=2;}rr r;} ll inv(ll a,ll m){ ll b=m,u=1,v=0; wh(b)u-=a/b*v,swap(u,v),a-=a/b*b,swap(a,b); rr(u%m+m)%m; } ll sqr(ll x){ll r=sqrtl(x)-1;wh(r+1<=x/(r+1))r++;rr r;} ll lg2(ll n){ll r=0;wh(n){n/=2;r++;}rr r;} u1 dx={-1,0,1,0,-1,1,1,-1}; u1 dy={0,-1,0,1,-1,-1,1,1}; ss edg{ll t,w;edg(){}edg(ll t,ll w=1):t(t),w(w){}}; uu graph=v2; vo GR(u2&g,ll m,bo d=1){rep(i,m){LL(a,b);a--;b--;g[a].eb(b);if(d)g[b].eb(a);}} vo GR(graph&g,ll m,bo w=1,bo d=1){ rep(i,m){ LL(a,b);a--;b--;ll c=1; if(w)lin(c); g[a].eb(b,c); if(d)g[b].eb(a,c); } } vo TR(u2&g,bo d=1){GR(g,len(g)-1,d);} vo TR(graph&g,bo w=1,bo d=1){GR(g,len(g)-1,w,d);} vo wf(u2&d){ll n=len(d);rep(k,n)rep(i,n)rep(j,n)amin(d[i][j],d[i][k]+d[k][j]);} uu S=ll; S emax(){rr-inf;} S emin(){rr inf;} S add(S a,S b){rr a+b;} S eadd(){rr 0;} S ope(S a,S b){rr a+b;} S einh(){rr 0;} uu seg_max=segtree; uu seg_min=segtree; uu seg_add=segtree; uu seg_oth=segtree; int main(){ LL(N); UL(N,a,b); vsrt([&](ll i,ll j){rr a[i]+b[i]*a[j]>a[j]+b[j]*a[i];},a,b); ll ans=0,lv=1; ll mod=1000000007; rep(i,N){ ans+=a[i]*lv;ans%=mod; lv*=b[i];lv%=mod; } pr(ans); }