#ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #include using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< bool chmax(t&a,u b){if(a bool chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os< void dmpr(ostream&os,const T&t,const Args&... args){ os< ostream& operator<<(ostream&os,const array&a){ return os<(all(a)); } template void print_tuple(ostream&,const T&){ } template void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<(t); print_tuple(os,t); } template ostream& operator<<(ostream&os,const tuple&t){ os<<"{"; print_tuple<0,tuple,Args...>(os,t); return os<<"}"; } template void print(t x,int suc=1){ cout<>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template void print(const pair&p,int suc=1){ print(p.a,2); print(p.b,suc); } template void print_offset(const pair&p,ll off,int suc=1){ print(p.a+off,2); print(p.b+off,suc); } template void print(const vector&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } template void print_offset(const vector&v,ll off,int suc=1){ rep(i,v.size()) print(v[i]+off,i==int(v.size())-1?suc:2); } template void print(const array&v,int suc=1){ rep(i,N) print(v[i],i==int(N)-1?suc:2); } string readString(){ string s; cin>>s; return s; } template T sq(const T& t){ return t*t; } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } //#define CAPITAL /* void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif }*/ void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int botbit(ull a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } int popcount(ull t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)< void mkuni(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution(l, r)(gen); } template void myshuffle(vc&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc readGraph(int n,int m){ vvc g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc readTree(int n){ return readGraph(n,n-1); } vc presum(const vi&a){ vc s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } //mint107 は verify してねえ //#define DYNAMIC_MOD struct modinfo{uint mod,root; #ifdef DYNAMIC_MOD constexpr modinfo(uint m,uint r):mod(m),root(r),im(0){set_mod(m);} ull im; constexpr void set_mod(uint m){ mod=m; im=ull(-1)/m+1; } uint product(uint a,uint b)const{ ull z=ull(a)*b; uint x=((unsigned __int128)z*im)>>64; uint v=uint(z)-x*mod; return v struct modular{ static constexpr uint const &mod=ref.mod; static modular root(){return modular(ref.root);} uint v; //modular(initializer_listls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(ll x,const modular&y){ return modular(x)+y; } friend modular operator-(ll x,const modular&y){ return modular(x)-y; } friend modular operator*(ll x,const modular&y){ return modular(x)*y; } friend modular operator/(ll x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v void inplace_fmt(const int n,mint*const f,bool inv){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static constexpr int L=30; static mint g[L],ig[L],p2[L]; if(g[0].v==0){ rep(i,L){ mint w=-mint::root().pow(((mod-1)>>(i+2))*3); g[i]=w; ig[i]=w.inv(); p2[i]=mint(1<>=1){//input:[0,mod) rep(i,b){ uint x=f[i+b].v; f[i+b].v=f[i].v+mod-x; f[i].v+=x; } } if(b>>=1){//input:[0,mod*2) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=1; for(int i=0,k=0;i void inplace_fmt(vector&f,bool inv){ inplace_fmt(si(f),f.data(),inv); } //size of input must be a power of 2 //output elements are in the range [0,mod*4) template void half_fmt(const int n,mint*const f){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static const int L=30; static mint g[L],h[L]; if(g[0].v==0){ rep(i,L){ g[i]=-mint::root().pow(((mod-1)>>(i+2))*3); h[i]=mint::root().pow((mod-1)>>(i+2)); } } int b=n; int lv=0; if(b>>=1){//input:[0,mod) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*2) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=h[lv++]; for(int i=0,k=0;i void half_fmt(vector&f){ half_fmt(si(f),f.data()); } #ifdef USE_GOOD_MOD template vc multiply(vc x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z; z.clear();z.resize(s); rep(i,si(y))z[i]=y[i]; inplace_fmt(z,false); rep(i,s)x[i]*=z[i]; }else{ rep(i,s)x[i]*=x[i]; } inplace_fmt(x,true);x.resize(n); return x; } template vc multiply_givenlength(vc x,const vc&y,bool same=false){ int s=si(x); assert(ispow2(s)); assert(si(y)); x.resize(s);inplace_fmt(x,false); if(!same){ vc z(s); rep(i,si(y))z[i]=y[i]; inplace_fmt(z,false); rep(i,s)x[i]*=z[i]; }else{ rep(i,s)x[i]*=x[i]; } inplace_fmt(x,true); return x; } #else //59501818244292734739283969-1=5.95*10^25 までの値を正しく計算 //最終的な列の大きさが 2^24 までなら動く //最終的な列の大きさが 2^20 以下のときは,下の 3 つの素数を使ったほうが速い(は?) //VERIFY: yosupo //Yukicoder No980 (same=true) namespace arbitrary_convolution{ constexpr modinfo base0{167772161,3};//2^25 * 5 + 1 constexpr modinfo base1{469762049,3};//2^26 * 7 + 1 constexpr modinfo base2{754974721,11};//2^24 * 45 + 1 //extern constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1 //extern constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1 //extern constexpr modinfo base2{1053818881,7};//2^20 * 1005 + 1 using mint0=modular; using mint1=modular; using mint2=modular; template vc sub(const vc&x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s);rep(i,si(x))z[i]=x[i].v; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i].v; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true);z.resize(n); return z; } template vc multiply(const vc&x,const vc&y,bool same=false){ auto d0=sub(x,y,same); auto d1=sub(x,y,same); auto d2=sub(x,y,same); int n=si(d0); vc res(n); static const mint1 r01=mint1(mint0::mod).inv(); static const mint2 r02=mint2(mint0::mod).inv(); static const mint2 r12=mint2(mint1::mod).inv(); static const mint2 r02r12=r02*r12; static const mint w1=mint(mint0::mod); static const mint w2=w1*mint(mint1::mod); rep(i,n){ ull a=d0[i].v; ull b=(d1[i].v+mint1::mod-a)*r01.v%mint1::mod; ull c=((d2[i].v+mint2::mod-a)*r02r12.v+(mint2::mod-b)*r12.v)%mint2::mod; res[i].v=(a+b*w1.v+c*w2.v)%mint::mod; } return res; } template vc sub_givenlength(const vc&x,const vc&y,bool same=false){ int s=si(x); assert(ispow2(s)); assert(si(y)==s); vc z(s);rep(i,si(x))z[i]=x[i].v; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i].v; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true); return z; } template vc multiply_givenlength(const vc&x,const vc&y,bool same=false){ auto d0=sub_givenlength(x,y,same); auto d1=sub_givenlength(x,y,same); auto d2=sub_givenlength(x,y,same); int n=si(d0); vc res(n); static const mint1 r01=mint1(mint0::mod).inv(); static const mint2 r02=mint2(mint0::mod).inv(); static const mint2 r12=mint2(mint1::mod).inv(); static const mint2 r02r12=r02*r12; static const mint w1=mint(mint0::mod); static const mint w2=w1*mint(mint1::mod); rep(i,n){ ull a=d0[i].v; ull b=(d1[i].v+mint1::mod-a)*r01.v%mint1::mod; ull c=((d2[i].v+mint2::mod-a)*r02r12.v+(mint2::mod-b)*r12.v)%mint2::mod; res[i].v=(a+b*w1.v+c*w2.v)%mint::mod; } return res; } } using arbitrary_convolution::multiply; using arbitrary_convolution::multiply_givenlength; #endif //UTPC2021 C namespace integer_convolution{ extern constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1 extern constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1 //extern constexpr modinfo base0{469762049,3};//2^26 * 7 + 1 //extern constexpr modinfo base1{754974721,11};//2^24 * 45 + 1 using mint0=modular; using mint1=modular; template vc sub(const vi&x,const vi&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s);rep(i,si(x))z[i]=x[i]; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i]; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true);z.resize(n); return z; } vi multiply(const vi&x,const vi&y,bool same=false){ auto d0=sub(x,y,same); auto d1=sub(x,y,same); const mint1 r=mint1(mint0::mod).inv(); const ll v=ll(mint0::mod)*mint1::mod; int n=si(d0); vi res(n); rep(i,n){ res[i]=d0[i].v+(r*(d1[i]-d0[i].v)).v*(ull)mint0::mod; if(res[i]>v/2)res[i]-=v; } return res; } } //最大で 1< vc large_convolution(const vc&a,const vc&b,int mx){ int n=si(a),m=si(b); vc c(n+m-1); int len=1<<(mx-1); for(int i=0;i(a.bg+i,a.bg+i+x),vc(b.bg+j,b.bg+j+y)); rep(k,si(d)) c[i+j+k]+=d[k]; } } return c; } //input A: N 次,B ?,M //output D: M 次多項式 //C を M 次多項式として //[x^N] A*B*C = [x^M] D*C //となるような D を返す //CF796F template vc transpose_advance(const vc&a,const vc&b,int m){ int n=si(a)-1; auto d=multiply(a,b); vc res(m+1); if(n>=m){ rep(i,m+1)res[i]=d[i+n-m]; }else{ rng(i,m-n,m+1)res[i]=d[i+n-m]; } return res; } template void chmult(vc&x,const vc&y,int s){ x=multiply(move(x),y); x.resize(s); } //Poly というのは常にサイズ 1 以上であることにしよう //low のあたりをかならずサイズ s のものを返すようにいじった //その影響で何かが起きているかも知れないし,起きていないかも知れない template struct Poly:public vc{ template Poly(Args...args):vc(args...){} Poly(initializer_listinit):vc(all(init)){} int size()const{ return vc::size(); } void ups(int s){ if(size()resize(s,0); } Poly low(int s)const{ assert(s); Poly res(s); rep(i,min(s,size()))res[i]=(*this)[i]; return res; } Poly rev()const{ auto r=*this; reverse(all(r)); return r; } Poly operator>>(int x)const{ assert(x Poly& operator+=(T t){ (*this)[0]+=t; return *this; } Poly& operator-=(const Poly&r){ ups(r.size()); rep(i,r.size()) (*this)[i]-=r[i]; return *this; } template Poly& operator-=(T t){ (*this)[0]-=t; return *this; } template Poly& operator*=(T t){ for(auto&v:*this) v*=t; return *this; } Poly& operator*=(const Poly&r){ return *this=multiply(*this,r); } Poly square()const{ return multiply(*this,*this,true); } #ifndef USE_GOOD_MOD Poly inv(int s)const{ Poly r{mint(1)/(*this)[0]}; for(int n=1;n f=low(2*n); f.resize(2*n); inplace_fmt(f,false); vc g=r.low(2*n); g.resize(2*n); inplace_fmt(g,false); rep(i,2*n)f[i]*=g[i]; inplace_fmt(f,true); rep(i,n)f[i]=0; inplace_fmt(f,false); rep(i,2*n)f[i]*=g[i]; inplace_fmt(f,true); rng(i,n,min(2*n,s))r[i]=-f[i]; } return r; } #endif template Poly& operator/=(T t){ return *this*=mint(1)/mint(t); } Poly quotient(const Poly&r,const Poly&rri)const{ int m=r.size(); assert(r[m-1].v); int n=size(); int s=n-m+1; if(s<=0) return {0}; return (rev().low(s)*rri.low(s)).low(s).rev(); } Poly& operator/=(const Poly&r){ return *this=quotient(r,r.rev().inv(max(size()-r.size(),int(0))+1)); } Poly& operator%=(const Poly&r){ *this-=*this/r*r; return *this=low(r.size()-1); } Poly operator+(const Poly&r)const{return Poly(*this)+=r;} template Poly operator+(T t)const{return Poly(*this)+=t;} Poly operator-(const Poly&r)const{return Poly(*this)-=r;} template Poly operator-(T t)const{return Poly(*this)-=t;} template Poly operator*(T t)const{return Poly(*this)*=t;} Poly operator*(const Poly&r)const{return Poly(*this)*=r;} template Poly operator/(T t)const{return Poly(*this)/=t;} Poly operator/(const Poly&r)const{return Poly(*this)/=r;} Poly operator%(const Poly&r)const{return Poly(*this)%=r;} Poly dif()const{ assert(size()); if(size()==1){ return {0}; }else{ Poly r(size()-1); rep(i,r.size()) r[i]=(*this)[i+1]*(i+1); return r; } } Poly inte(const mint invs[])const{ Poly r(size()+1,0); rep(i,size()) r[i+1]=(*this)[i]*invs[i+1]; return r; } //VERIFY: yosupo //opencupXIII GP of Peterhof H Poly log(int s,const mint invs[])const{ assert((*this)[0]==1); if(s==1)return {0}; return (low(s).dif()*inv(s-1)).low(s-1).inte(invs); } //Petrozavodsk 2019w mintay1 G //yosupo judge //UOJ Round23 C Poly exp(int s,const mint invs[])const{ assert((*this)[0]==mint(0)); Poly f{1},g{1}; for(int n=1;;n*=2){ if(n>=s)break; g=g*2-(g.square()*f).low(n); //if(n>=s)break; Poly q=low(n).dif(); q=q+g*(f.dif()-f*q).low(2*n-1); f=f+(f*(low(2*n)-q.inte(invs))).low(2*n); } return f.low(s); } //exp(x),exp(-x) のペアを返す //UOJ Round23 C pair exp2(int s,const mint invs[])const{ assert((*this)[0]==mint(0)); Poly f{1},g{1}; for(int n=1;;n*=2){ //if(n>=s)break; g=g*2-(g.square()*f).low(n); if(n>=s)break; Poly q=low(n).dif(); q=q+g*(f.dif()-f*q).low(2*n-1); f=f+(f*(low(2*n)-q.inte(invs))).low(2*n); } return make_pair(f.low(s),g.low(s)); } #ifndef USE_GOOD_MOD //CF250 E Poly sqrt(int s)const{ assert((*this)[0]==1); static const mint half=mint(1)/mint(2); Poly r{1}; for(int n=1;n f{1},g{1},z{1}; for(int n=1;n delta(2*n); rep(i,n)delta[n+i]=z[i]-freq(i)-freq(n+i); inplace_fmt(delta,false); vc gbuf(2*n); rep(i,n)gbuf[i]=g[i]; inplace_fmt(gbuf,false); rep(i,2*n)delta[i]*=gbuf[i]; inplace_fmt(delta,true); f.resize(2*n); rng(i,n,2*n)f[i]=-half*delta[i]; if(2*n>=s)break; z=f; inplace_fmt(z,false); vc eps=gbuf; rep(i,2*n)eps[i]*=z[i]; inplace_fmt(eps,true); rep(i,n)eps[i]=0; inplace_fmt(eps,false); rep(i,2*n)eps[i]*=gbuf[i]; inplace_fmt(eps,true); g.resize(2*n); rng(i,n,2*n)g[i]=-eps[i]; } f.resize(s); return f; } #endif pair divide(const Poly&r,const Poly&rri)const{ Poly a=quotient(r,rri); Poly b=*this-a*r; return make_pair(a,b.low(r.size()-1)); } //Yukicoder No.215 Poly pow_mod(int n,const Poly&r)const{ Poly rri=r.rev().inv(r.size()); Poly cur{1},x=*this%r; while(n){ if(n%2) cur=(cur*x).divide(r,rri).b; x=(x*x).divide(r,rri).b; n/=2; } return cur; } int lowzero()const{ rep(i,size())if((*this)[i]!=0)return i; return size(); } //VERIFY: yosupo //UOJ Round23 C (z=0,p<0) Poly pow(int s,int p,const mint invs[])const{ assert(s>0); int n=size(),z=0; for(;z=0); if(z*p>=s)return Poly(s,0); mint c=(*this)[z],cinv=c.inv(); mint d=c.pow(p); int t=s-z*p; Poly x(t); rng(i,z,min(z+t,n))x[i-z]=(*this)[i]*cinv; x=x.log(t,invs); rep(i,t)x[i]*=p; x=x.exp(t,invs); rep(i,t)x[i]*=d; Poly y(s); rep(i,t)y[z*p+i]=x[i]; return y; } mint eval(mint x)const{ mint r=0,w=1; for(auto v:*this){ r+=w*v; w*=x; } return r; } }; //CF641 F2 //f*x^(-a) template struct Laurent{ Poly f; int a; Laurent(const Poly&num,const Poly&den,int s){ a=den.lowzero(); assert(a>a).inv(s)).low(s); } Laurent(const Poly&ff,int aa):f(ff),a(aa){} Laurent dif()const{ return Laurent(f*(-a)+(f.dif()<<1),a+1); } mint&operator[](int i){ assert(inc(0,i+a,si(f)-1)); return f[i+a]; } }; template ll m2l(mint a){ return a.v void showpoly(const Poly&a){ vi tmp(si(a)); rep(i,si(a)){ tmp[i]=m2l(a[i]); } cerr<; #endif using mint=modular; mint parity(int i){ return i%2==0?1:-1; } #ifdef LOCAL const int vmax=1010; #else const int vmax=(1<<21)+10; #endif mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax){ fact[i]=fact[i-1]*i; } finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=0;i--){ finv[i]=finv[i+1]*(i+1); } for(int i=vmax-1;i>=1;i--){ invs[i]=finv[i]*fact[i-1]; } } mint choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } /* const int vmax=110; mint binbuf[vmax][vmax]; mint choose(int n,int k){ return binbuf[n-k][k]; } mint binom(int a,int b){ return binbuf[a][b]; } void initfact(){ binbuf[0][0]=1; rep(i,vmax)rep(j,vmax){ if(i)binbuf[i][j]+=binbuf[i-1][j]; if(j)binbuf[i][j]+=binbuf[i][j-1]; } } */ mint p2[vmax],p2inv[vmax]; void initp2(){ p2[0]=1; rep(i,vmax-1)p2[i+1]=p2[i]*2; p2inv[vmax-1]=p2[vmax-1].inv(); per(i,vmax-1)p2inv[i]=p2inv[i+1]*2; } //verify yosupo vc sampling_shift(vc a,mint c,int m){ int n=si(a); rep(i,n)a[i]*=finv[i]; vc b(finv,finv+n); rep(i,n)b[i]*=parity(i); chmult(a,b,n); rep(i,n)a[i]*=fact[i]; reverse(all(a)); mint w=1; rep(i,n){ b[i]=finv[i]*w; w*=(c-i); } chmult(a,b,n); reverse(all(a)); rep(i,n)a[i]*=finv[i]; a.resize(m); b.resize(m); rep(i,m)b[i]=finv[i]; chmult(a,b,m); rep(i,m)a[i]*=fact[i]; return a; } void extend_poly(vc&a,int m){ int n=si(a); rep(i,n)a[i]*=finv[i]; vc b(finv,finv+n); rep(i,n)b[i]*=parity(i); chmult(a,b,n); a.resize(m); b.resize(m); rep(i,m)b[i]=finv[i]; chmult(a,b,m); rep(i,m)a[i]*=fact[i]; } void extend_polys(vvc&as,int m){ int n=si(as[0]); for(auto&a:as)assert(si(a)==n); for(auto&a:as)rep(i,n)a[i]*=finv[i]; vc b(finv,finv+n); rep(i,n)b[i]*=parity(i); for(auto&a:as)chmult(a,b,n); for(auto&a:as)a.resize(m); b.resize(m); rep(i,m)b[i]=finv[i]; for(auto&a:as)chmult(a,b,m); for(auto&a:as)rep(i,m)a[i]*=fact[i]; } struct large_factorial{ int s; vc x; large_factorial():s(1),x(1,1){ while(sq(s) rw,buf; static int getp2(int v){ return 1<<(topbit(v-1)+1); } F():n(0){} F(const vc&given):rw(given){ n=si(rw); assert(n>0); } F(initializer_list init):rw(all(init)){ n=si(rw); assert(n>0); } int size()const{return n;} bool empty()const{return n==0;} void assume_have(){ if(rw.empty()){ int s=getp2(n); assert(si(buf)>=s); rw.resize(s); rep(i,s)rw[i]=buf[i].v; inplace_fmt(rw,true); rw.resize(n); } assert(si(rw)==n); } vc getrw(){ assume_have(); return rw; } void prepare(int len){ if(si(buf)=s&&si(b.buf)>=s){ buf.resize(s); rep(i,s)buf[i]=mint(a.buf[i].v)+mint(b.buf[i].v); }else buf.clear(); if(rw.empty()&&buf.empty()){ a.prepare(n); b.prepare(n); buf.resize(s); rep(i,s)buf[i]=mint(a.buf[i].v)+mint(b.buf[i].v); } } void init_from_product(F&a,F&b){ assert(a.n>0); assert(b.n>0); n=a.n+b.n-1; rw.clear(); int s=getp2(n); a.prepare(n); b.prepare(n); buf.resize(s); rep(i,s)buf[i]=a.buf[i]*b.buf[i]; } F operator*(F&b){ F res; res.init_from_product(*this,b); return res; } F operator+(F&b){ F res; res.init_from_sum(*this,b); return res; } F operator+(F&&b){ F res; res.init_from_sum(*this,b); return res; } F& operator*=(F&b){ return *this=(*this)*b; } F& operator+=(F&b){ return *this=(*this)+b; } F& operator+=(F&&b){ return *this=(*this)+b; } }; //転置原理 //a,b: x の多項式 //n=deg(a),m=deg(b) //a*b の各係数に何かをかけたものが答え(に寄与),という状況があったとする //これは適当な関数 c があって,ans+=[x^{n+m}] a*b*c という風に書ける //b が入力で固定されているならば,deg(d)=n なる多項式 d であって, //ans+=[x^n] a*d となるものがある //そのような d を持ってくる F middle(F&b,F&c){ int m=si(b)-1,nm=si(c)-1,n=nm-m; assert(n>=0); int s=F::getp2(nm+1); b.prepare(s); c.prepare(s); static vc buf; buf.resize(s); rep(i,s)buf[i]=b.buf[i]*c.buf[i]; inplace_fmt(buf,true); rep(i,n+1)buf[i]=buf[i+m]; buf.resize(n+1); return F(buf); } void slv1(int t){ using V=array; using M=array; int kmax=0; vc nk(t); for(auto&[n,k]:nk){ cin>>n>>k; n%=mint::mod; chmax(kmax,k); } vc qs; rep(i,kmax)qs.eb(i,inf); rep(i,t)qs.eb(nk[i].b,i); sort(all(qs)); int s=si(qs); using T=tuple; vc buf(2*s); auto getid=[&](int l,int r){ if(r-l==1)return l+r; else return (l+r)/2*2; }; { auto dfs=[&](auto self,int l,int r)->void{ auto&[a,b]=buf[getid(l,r)]; if(r-l==1){ if(qs[l].b rw=b.getrw(); rw.erase(rw.bg,rw.bg+kmax); rw=rw.inv(kmax+1); rw.resize(s); rotate(rw.bg,rw.bg+kmax+1,rw.ed); ini[0]=rw; ini[1]=vc(s); } vc ans(t); { auto dfs=[&](auto self,int l,int r,V z)->void{ rep(k,2)assert(si(z[k])==r-l); if(r-l==1){ mint val=z[0].getrw()[0]; if(qs[l].b>n>>k; if(k>=mint::mod)return print(0); n%=mint::mod; vvc a(4); rep(i,3){ a[0].pb(2*n-2*i); a[1].pb((n-(i-1)*invs[2])*i); a[2].pb(1); a[3].pb(0); } int s=1; while(s*(2*s+1)>t; if(t<=5){rep(_,t)slv2();} else{slv1(t);} }