//#ifdef ONLINE_JUDGE #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include //#endif #include #define bg(a) begin(a) #define ed(a) end(a) #define rbg(a) rbegin(a) #define red(a) rend(a) #define fro() front() #define bck() back() #define fin(...) exit(pp(__VA_ARGS__)) #define ep(...) emplace(__VA_ARGS__) #define eb(...) emplace_back(__VA_ARGS__) #define pb() pop_back() #define ef(...) emplace_front(__VA_ARGS__) #define pf(...) pop_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 itmax(...) max_element(al(__VA_ARGS__)) #define itmin(...) min_element(al(__VA_ARGS__)) #define srt(...) sort(al(__VA_ARGS__)) #define rev(...) reverse(al(__VA_ARGS__)) #define uq(a) srt(a);a.erase(unique(al(a)),ed(a)) #define jo(a,b) copy(al(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 al1(v) bg(v),ed(v) #define al2(v,b) bg(v),bg(v)+b #define al3(v,a,b) bg(v)+a,bg(v)+b #define al(...) ov3(__VA_ARGS__,al3,al2,al1)(__VA_ARGS__) #define rl1(v) rbg(v),red(v) #define rl2(v,b) rbg(v),rbg(v)+b #define rl3(v,a,b) rbg(v)+a,rbg(v)+b #define rl(...) ov3(__VA_ARGS__,rl3,rl2,rl1)(__VA_ARGS__) #define fo1(b) for(ll ii=0;ii<(ll)(b);ii++) #define fo2(i,b) for(ll i=0;i<(ll)(b);i++) #define fo3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define fo4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c)) #define fo(...) ov4(__VA_ARGS__,fo4,fo3,fo2,fo1)(__VA_ARGS__) #define of1(a) fo(a) #define of2(i,a) for(ll i=(ll)(a)-1;i>=0;i--) #define of3(i,a,b) for(ll i=(ll)(a)-1;i>=(ll)(b);i--) #define of4(i,a,b,c) for(ll i=(ll)(a)-1;i>=(ll)(b);i-=(ll)(c)) #define of(...) ov4(__VA_ARGS__,of4,of3,of2,of1)(__VA_ARGS__) #define fe1(a) fo(len(a)) #define fe2(a,v) for(au&&a:v) #define fe3(a,b,v) for(au&&[a,b]:v) #define fe4(a,b,c,v) for(au&&[a,b,c]:v) #define fe5(a,b,c,d,v) for(au&&[a,b,c,d]:v) #define fe(...) ov5(__VA_ARGS__,fe5,fe4,fe3,fe2,fe1)(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;li(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;li(__VA_ARGS__) #define STR(...) str __VA_ARGS__;li(__VA_ARGS__) #define UL2(n,a) u1 a(n);li(a) #define UL3(n,a,b) u1 a(n),b(n);li(a,b) #define UL4(n,a,b,c) u1 a(n),b(n),c(n);li(a,b,c) #define UL5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);li(a,b,c,d) #define UL6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);li(a,b,c,d,e) #define UL(...) ov6(__VA_ARGS__,UL6,UL5,UL4,UL3,UL2)(__VA_ARGS__) #define UV2(n,a) u1 a(n);vi(a) #define UV3(n,a,b) u1 a(n),b(n);vi(a,b) #define UV4(n,a,b,c) u1 a(n),b(n),c(n);vi(a,b,c) #define UV5(n,a,b,c,d) u1 a(n),b(n),c(n),d(n);vi(a,b,c,d) #define UV6(n,a,b,c,d,e) u1 a(n),b(n),c(n),d(n),e(n);vi(a,b,c,d,e) #define UV(...) ov6(__VA_ARGS__,UV6,UV5,UV4,UV3,UV2)(__VA_ARGS__) #define DL2(n,a) v1a(n);li(a) #define DL3(n,a,b) v1a(n),b(n);li(a,b) #define DL4(n,a,b,c) v1a(n),b(n),c(n);li(a,b,c) #define DL5(n,a,b,c,d) v1a(n),b(n),c(n),d(n);li(a,b,c,d) #define DL(...) ov5(__VA_ARGS__,DL5,DL4,DL3,DL2)(__VA_ARGS__) #define DV2(n,a) v1a(n);vi(a) #define DV3(n,a,b) v1a(n),b(n);vi(a,b) #define DV4(n,a,b,c) v1a(n),b(n),c(n);vi(a,b,c) #define DV5(n,a,b,c,d) v1a(n),b(n),c(n),d(n);vi(a,b,c,d) #define DV(...) ov5(__VA_ARGS__,DV5,DV4,DV3,DV2)(__VA_ARGS__) #define aa2(a,b) ((a) an (b)) #define aa3(a,b,c) ((a) an (b) an (c)) #define aa4(a,b,c,d) ((a) an (b) an (c) an (d)) #define aa5(a,b,c,d,e) ((a) an (b) an (c) an (d) an (e)) #define aa6(a,b,c,d,e,f) ((a) an (b) an (c) an (d) an (e) an (f)) #define aa(...) ov6(__VA_ARGS__,aa6,aa5,aa4,aa3,aa2)(__VA_ARGS__) #define oo2(a,b) ((a) or (b)) #define oo3(a,b,c) ((a) or (b) or (c)) #define oo4(a,b,c,d) ((a) or (b) or (c) or (d)) #define oo5(a,b,c,d,e) ((a) or (b) or (c) or (d) or (e)) #define oo6(a,b,c,d,e,f) ((a) or (b) or (c) or (d) or (e) or (f)) #define oo(...) ov6(__VA_ARGS__,oo6,oo5,oo4,oo3,oo2)(__VA_ARGS__) #define I template #define J class #define rr return #define ss struct #define uu using #define an and #define as assert #define au auto #define bk break #define cs const #define ct continue #define endl "\n" #define fd friend #define op operator #define stc static #define th this namespace my{void solve();} int main(){my::solve();} namespace my{ //#ifdef ONLINE_JUDGE uu namespace atcoder; uu namespace boost::multiprecision; uu mint=modint1000000007; //endif uu namespace std; uu ll=long long; uu ld=long double; uu ul=unsigned long long; uu cha=char; uu str=string; uu bo=bool; uu vo=void; uu is=istream; uu os=ostream; str sp=" ",nc="",nl="\n"; au np=nullptr; Iss cp{ A a;B b; cp():a(A()),b(B()){} cp(A a,B b):a(a),b(b){} cp op+()cs{rr*th;} cp op-()cs{rr cp(-a,-b);} cp&op++(){a++,b++;rr*th;}cp op++(int){cp r=*th;++*th;rr r;} cp&op--(){a--,b--;rr*th;}cp op--(int){cp r=*th;--*th;rr r;} cp&op+=(cs cp&c){a+=c.a;b+=c.b;rr*th;}cp op+(cs cp&c)cs{rr cp(*th)+=c;} cp&op-=(cs cp&c){a-=c.a;b-=c.b;rr*th;}cp op-(cs cp&c)cs{rr cp(*th)-=c;} cp&op*=(cs cp&c){a*=c.a;b*=c.b;rr*th;}cp op*(cs cp&c)cs{rr cp(*th)*=c;} cp&op+=(cs A&d){a+=d;b+=d;rr*th;}cp op+(cs A&d)cs{rr cp(*th)+=d;} cp&op-=(cs A&d){a-=d;b-=d;rr*th;}cp op-(cs A&d)cs{rr cp(*th)-=d;} cp&op*=(cs A&d){a*=d;b*=d;rr*th;}cp op*(cs A&d)cs{rr cp(*th)*=d;} bo op==(cs cp&c)cs{rr aa(a==c.a,b==c.b);}bo op!=(cs cp&c)cs{rr!(*th==c);} bo op<(cs cp&c)cs{rr a!=c.a?a=(cs cp&c)cs{rr!(*th(cs cp&c)cs{rr a!=c.a?a>c.a:b>c.b;}bo op<=(cs cp&c)cs{rr!(*th>c);} fd is&op>>(is&i,cp&c){rr i>>c.a>>c.b;} fd os&op<<(os&o,cs cp&c){rr o<ss tr{ A a;B b;C c; tr():a(A()),b(B()),c(C()){} tr(A a,B b,C c):a(a),b(b),c(c){} bo op==(cs tr&t)cs{rr aa(a==t.a,b==t.b,c==t.c);} bo op!=(cs tr&t)cs{rr!(*th==t);} bo op<(cs tr&t)cs{rr a!=t.a?a(cs tr&t)cs{rr a!=t.a?a>t.a:b!=t.b?b>t.b:c>t.c;} fd is&op>>(is&i,tr&t){rr i>>t.a>>t.b>>t.c;} fd os&op<<(os&o,cs tr&t){rr o<ss qu{ A a;B b;C c;D d; qu():a(A()),b(B()),c(C()),d(D()){} qu(A a,B b,C c,D d):a(a),b(b),c(c),d(d){} bo op==(cs qu&q)cs{rr aa(a==q.a,b==q.b,c==q.c,d==q.d);} bo op!=(cs qu&q)cs{rr!(*th==q);} bo op<(cs qu&q)cs{rr a!=q.a?a(cs qu&q)cs{rr a!=q.a?a>q.a:b!=q.b?b>q.b:c!=q.c?c>q.c:d>q.d;} fd is&op>>(is&i,qu&q){rr i>>q.a>>q.b>>q.c>>q.d;} fd os&op<<(os&o,cs qu&q){rr o<uu v1=vector;uu u1=v1; Iuu v2=v1>;uu u2=v1; Iuu v3=v1>;uu u3=v1; Iuu v4=v1>;uu u4=v1; Iuu mset=multiset; Iuu fn=function; Iuu pqmax=priority_queue; Iuu pqmin=priority_queue,greater>; uu strs=v1; uu cl=cp; uu cd=cp; uu ql=queue; uu sl=set; uu msl=mset; uu ml=map; ss edg{ll t,w;edg(){}edg(ll t,ll w=1):t(t),w(w){}}; uu graph=v2; ll inf=3e18; ld ee=1e-10,pi=acosl(-1); u1 dx={-1,0,1,0,-1,1,1,-1},dy={0,-1,0,1,-1,-1,1,1}; 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 no(){rr "no";} str Yes(bo t=1){rr t?"Yes":"No";}str No(){rr "No";} str YES(bo t=1){rr t?"YES":"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";} ul rnd(){ stc ul x=123456789,y=362436069,z=521288629,w=88675123; ul t=(x^(x<<11)); x=y,y=z,z=w; rr(w=(w^(w>>19))^(t^(t>>8))); } ld rnd_prob(){rr (ld)rnd()/ULLONG_MAX;} ll rnd_rng(ll r){rr rnd()%r;} ll rnd_rng(ll l,ll r){rr rnd()%(r-l)+l;} ll bit(ll a){rr 1LL<str tstr(T a){rr to_string(a);} Istr tstr(T a,A...b){rr tstr(a)+tstr(b...);} Ill len(cs T&a){rr a.size();} IT sq(T a){rr a*a;} Iau cei(T a,U b){rr (a+b-1)/b;} 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 sgn(cs T&a){rr(a>ee)-(a<-ee);} Ill sgn(cs T&a,cs U&b){rr sgn(a-b);} Iau&op+(v1&v){rr v;} Iau&op-(v1&v){fe(x,v)x=-x;rr v;} Iau&op++(v1&v){fe(x,v)x++;rr v;} Iau&op--(v1&v){fe(x,v)x--;rr v;} Iau op++(v1&v,int){au r=v;++v;rr r;} Iau op--(v1&v,int){au r=v;--v;rr r;} Iau&op+=(v1&v,cs v1&u){fo(i,len(v))v[i]+=u[i];rr v;} Iau&op-=(v1&v,cs v1&u){fo(i,len(v))v[i]-=u[i];rr v;} Iau&op*=(v1&v,cs v1&u){fo(i,len(v))v[i]*=u[i];rr v;} Iau op+(v1v,cs v1&u){rr v+=u;} Iau op-(v1v,cs v1&u){rr v-=u;} Iau op*(v1v,cs v1&u){rr v*=u;} Iau&op+=(v1&v,cs U&a){fe(x,v)x+=a;rr v;} Iau&op-=(v1&v,cs U&a){fe(x,v)x-=a;rr v;} Iau&op*=(v1&v,cs U&a){fe(x,v)x*=a;rr v;} Iau op+(v1v,cs U&a){rr v+=a;} Iau op-(v1v,cs U&a){rr v-=a;} Iau op*(v1v,cs U&a){rr v*=a;} 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 *itmax(a);} IT min(cs v1&a){rr *itmin(a);} Iau max(cs v2&a){rr max(*itmax(a));} Iau min(cs v2&a){rr min(*itmin(a));} Iau max(T...a){rr max(initializer_list>{a...});} Iau min(T...a){rr min(initializer_list>{a...});} Ill argmax(cs v1&a){rr itmax(a)-bg(a);} Ill argmin(cs v1&a){rr itmin(a)-bg(a);} IT gcd(cs T&a,cs A&...b){rr gcd(a,gcd(b...));} IT sum(cs v1&a){rr accumulate(al(a),T(0));} Ill lbs(cs v1&a,cs U&b){rr lb(al(a),b)-bg(a);} Ill ubs(cs v1&a,cs U&b){rr ub(al(a),b)-bg(a);} Iau minmax(cs T&a,cs U&b){rr cp(min(a,b),max(a,b));} Iau minmax(cs cp&p){rr minmax(p.a,p.b);} Ivo emplace_front(v1&v,T x=0){v.ep(bg(v),x);} Ivo pop_front(v1&v){v.erase(bg(v));} Iau mp(cs fn&f,v1x){v1y;fe(a,x)y.eb(f(a));rr y;} Iau keys(cs map&m){v1r;fe(k,z,m)r.eb(k);rr r;} Iau vals(cs map&m){v1r;fe(z,v,m)r.eb(v);rr r;} u1 io(ll n,ll a=0){u1 i(n);iota(al(i),a);rr i;} IT gp(queue&q){T r=q.fro();q.pop();rr r;} IT gp(pqmax&q){T r=q.top();q.pop();rr r;} IT gp(pqmin&q){T r=q.top();q.pop();rr r;} ss z{z(){cin.tie(0);ios::sync_with_stdio(0);cout<>(is&i,mint&x){ll t;i>>t;x=t;rr i;} os&op<<(os&o,cs mint&x){rr o<is&op>>(is&i,pair&p){rr i>>p.first>>p.second;} Ios&op<<(os&o,cs pair&p){rr o<is&op>>(is&i,v1&v){fe(x,v)i>>x;rr i;} Ios&op<<(os&o,cs v1&v){fe(x,v)o<os&op<<(os&o,cs v2&v){fe(x,v)o<os&op<<(os&o,cs set&s){fe(x,s)o<os&op<<(os&o,cs mset&s){fe(x,s)o<os&op<<(os&o,cs map&m){fe(p,m)o<os&op<<(os&o,queueq){wh(len(q))o<os&op<<(os&o,dequeq){wh(len(q))o<os&op<<(os&o,pqmaxq){wh(len(q))o<os&op<<(os&o,pqminq){wh(len(q))o<ll pp(cs T&a,cs A&...b){cout<vo li(T&...a){(cin>>...>>a);} Ivo vi(ll i,T&...a){(cin>>...>>a[i]);} Ivo vi(v1&a,A&...b){fo(i,len(a))vi(i,a,b...);} Ivo rs(v1&v,ll n){v.resize(n);} Ivo rs(v1&V,ll n,cs A&...a){rs(V,n);fe(v,V)rs(v,a...);} Ivo fl(T&x,cs U&a){x=a;} Ivo fl(v1&V,cs U&a){fe(v,V)fl(v,a);} vo gi(u2&g,ll m,bo d=1){fo(i,m){LL(a,b);a--,b--;g[a].eb(b);if(d)g[b].eb(a);}} vo gi(graph&g,ll m,bo w=1,bo d=1){ fo(i,m){ LL(a,b);a--,b--;ll c=1;if(w)li(c); g[a].eb(b,c);if(d)g[b].eb(a,c); } } vo ti(u2&g,bo d=1){gi(g,len(g)-1,d);} vo ti(graph&g,bo w=1,bo d=1){gi(g,len(g)-1,w,d);} vo pz(cs u1&v,u1&h){fe(x,h)x=lbs(v,x);} Ivo pz(cs u1&v,u1&h,T&...t){pz(v,h);pz(v,t...);} Iu1 zp(T&...a){u1 v;fe(e,{a...})jo(v,e);uq(v);pz(v,a...);rr v;} Ivo vs(cs u1&o,v1&a){au c=a;fo(i,len(a))a[i]=c[o[i]];} Ivo vs(cs u1&o,v1&a,A&...b){vs(o,a);vs(o,b...);} Iau vs(cs fn&f,T&...a){ ll n=0;fe(e,{a...})n=len(e); u1 o=io(n),p(n); sort(al(o),f); fo(i,n)p[o[i]]=i; vs(o,a...); rr cp(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){fo(i,1,len(a))a[i]+=a[i-1];rr a;} Iau mb(v1a){of(i,len(a),1)a[i]-=a[i-1];rr a;} Iau zt(v2a){fe(v,a)v=zt(v);fo(i,1,len(a))a[i]+=a[i-1];rr a;} Iau mb(v2a){fe(v,a)v=mb(v);of(i,len(a),1)a[i]-=a[i-1];rr a;} IT exq(T x,ll n,T e){wh(n){if(n&1)e*=x;x*=x;n/=2;}rr e;} vo wafl(u2&d){ll n=len(d);fo(k,n)fo(i,n)fo(j,n)amin(d[i][j],d[i][k]+d[k][j]);} u1 divs(ll n){ml m;fo(i,1,n/i+1)if(n%i==0)m[i]++,m[n/i]++;rr keys(m);} ml fact(ll n){ml m;fo(i,2,n/i+1)wh(n%i==0)m[i]++,n/=i;if(n>1)m[n]++;rr m;} ll pow(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; } Ill mrgc(v1&a){ ll n=len(a); if(n<=1)rr 0; v1b(al(a,n/2)),c(al(a,n/2,n)); ll cnt=mrgc(b)+mrgc(c); for(ll i=0,j=0,k=0;ill invc(v1a){rr mrgc(a);} u1 djks(cs graph&g,ll s){ ll n=len(g); u1 d(n,inf);d[s]=0; pqminq;q.ep(0,s); wh(len(q)){ au[du,u]=gp(q); if(d[u]ss com{ v1fa,ra,bs; v2m; v2u; com(ll n){ n++; rs(fa,n);rs(ra,n);rs(bs,n); fa[0]=ra[0]=bs[0]=1; fo(i,1,n)fa[i]=fa[i-1]*i,ra[i]=ra[i-1]/i; fo(i,1,n)bs[i]=bs[i-1]+ra[i]*pow(-1,i&1); if(n<=5e3)rs(m,n,n),rs(u,n,n); } T c(ll n,ll k){rr oo(n=0)rr u[n][k]=1,m[n][k]=p(n,k-1)+p(n-k,k); el rr u[n][k]=1,m[n][k]=p(n,k-1); } }; ss ufd{ ll n; u1 d; ufd():n(0){} ufd(ll n):n(n),d(n,-1){} ll top(ll a){as(aa(0<=a,a&f,cs fn&e>ss sgt{ ll n,A,log; v1d; sgt(ll n):sgt(v1(n,e())){} sgt(cs v1&v):n(len(v)){ log=lg2(n*2-1)-1; A=bit(log); d=v1(A*2,e()); fo(i,n)d[i+A]=v[i]; of(i,A,1)upd(i); } vo upd(ll k){d[k]=f(d[k*2],d[k*2+1]);} vo set(ll i,S x){as(aa(0<=i,i>j);} vo add(ll i,S x){as(aa(0<=i,is(N); fo(i,N)s[i]=(i?s[i-1]:1)*a[i]; mint ans=0; fo(i,N-1)ans+=s[i]*mint(3).pow(N-2-i)*2; pp(ans+s.bck()); }}