代码

#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#pragma GCC optimize("-fno-math-errno")
#pragma GCC optimize("-funsafe-math-optimizations")
#pragma GCC optimize("-freciprocal-math")
#pragma GCC optimize("-fno-trapping-math")
#pragma GCC optimize("-ffinite-math-only")
#pragma GCC optimize("-fno-stack-protector")
#pragma GCC target ("avx2","sse4.2","fma")
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
#define inline __attribute__((__gnu_inline__, __always_inline__, __artificial__)) inline
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long; 
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int T; cin >> T; while ( T -- )
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
namespace __POLY__ {
	const int mod = 998244353, proot = 3;
	typedef int i32;typedef unsigned int u32;typedef long long i64;typedef unsigned long long u64;typedef vector<i32>vi32;typedef vector<u32>vu32;typedef vector<i64>vi64;typedef vector<u64>vu64;namespace math{template<typename T=int>inline T qp(i64 x,int y,i64 ans=1){for(y<0?y+=mod-1:0;y;y>>=1,x=x*x%mod)y&1?ans=ans*x%mod:0;return ans;}inline constexpr int lg(u32 x){return x==0?-1:((int)sizeof(int)*__CHAR_BIT__-1-__builtin_clz(x));}inline u32 fst_mul(u32 x,u64 p,u64 q){return x*p-(q*x>>32)*mod;}const u32 modm2=mod+mod;namespace basic_math{vu32 __fac({1,1}),__ifc({1,1}),__inv({0,1});inline void __prep(int n){static int i=2;if(i<n)for(__fac.resize(n),__ifc.resize(n),__inv.resize(n);i<n;i++)__fac[i]=1ll*i*__fac[i-1]%mod,__inv[i]=1ll*(mod-mod/i)*__inv[mod%i]%mod,__ifc[i]=1ll*__inv[i]*__ifc[i-1]%mod;}inline u32 gfac(u32 x){return __prep(x+1),__fac[x];}inline u32 gifc(u32 x){return __prep(x+1),__ifc[x];}inline u32 ginv(u32 x){return __prep(x+1),__inv[x];}inline u32 gC(u32 n,u32 m){if(n<m)return 0;return 1ll*gfac(n)*gifc(m)%mod*gifc(n-m)%mod;}}namespace cipolla{u32 I=0;struct cpl{u32 x,y;cpl(u32 _x=0,u32 _y=0):x(_x),y(_y){}inline cpl operator*(const cpl&a)const{return cpl((1ull*x*a.x+1ull*I*y%mod*a.y)%mod,(1ull*x*a.y+1ull*y*a.x)%mod);}};inline cpl cplpow(cpl a,int y,cpl b=cpl(1,0)){for(;y;y>>=1,a=a*a)if(y&1)b=b*a;return b;}inline u32 isqrt(u32 x){static mt19937 rnd(998244353);if(mod==2||!x||x==1)return x;u32 a=0;do{a=rnd()%mod;}while(qp((1ull*a*a+mod-x)%mod,mod>>1)!=mod-1);I=(1ll*a*a+mod-x)%mod;a=cplpow(cpl(a,1),(mod+1)>>1).x;return min(a,mod-a);}}using basic_math::gfac;using basic_math::gifc;using basic_math::ginv;using cipolla::isqrt;}namespace polynomial{const int maxbit=21;using math::gfac;using math::gifc;using math::ginv;using math::lg;using math::qp;
	namespace fast_number_theory_transform{using math::fst_mul;using math::modm2;u32 pool[(1<<23)*4]__attribute__((aligned(64))),*ptr=pool;u32*p0[(1<<23)],*p1[(1<<23)],*q0[(1<<23)],*q1[(1<<23)];__attribute__((always_inline))inline void bit_flip(u32*p,int t){for(int i=0,j=0;i<t;++i){if(i>j)swap(p[i],p[j]);for(int l=t>>1;(j^=l)<l;l>>=1);}}void prep(int n){static int t=1;for(;t<n;t<<=1){int g=qp(3,(mod-1)/(t*2));u32*p,*q;p=p0[t]=ptr;ptr+=max(t,16);p[0]=1;for(int m=1;m<t;++m)p[m]=p[m-1]*(ull)g%u32(mod);bit_flip(p,t);q=q0[t]=ptr;ptr+=max(t,16);for(int i=0;i<t;++i)q[i]=(ull(p[i])<<32)/mod;g=qp(g,mod-2);p=p1[t]=ptr;ptr+=max(t,16);p[0]=1;for(int m=1;m<t;++m)p[m]=p[m-1]*(ull)g%u32(mod);bit_flip(p,t);q=q1[t]=ptr;ptr+=max(t,16);for(int i=0;i<t;++i)q[i]=(ull(p[i])<<32)/mod;}}typedef unsigned long long ull;__attribute__((always_inline))inline u32 my_mul(u32 a,u32 b,u32 c){return b*(ull)a-((ull(a)*c)>>32)*ull(998244353);}__attribute__((always_inline))inline __m128i my_mullo_epu32(const __m128i&a,const __m128i&b){return(__m128i)((__v4su)a*(__v4su)b);}__attribute__((always_inline))inline __m128i my_mulhi_epu32(const __m128i&a,const __m128i&b){__m128i a13=_mm_shuffle_epi32(a,0xF5);__m128i b13=_mm_shuffle_epi32(b,0xF5);__m128i prod02=_mm_mul_epu32(a,b);__m128i prod13=_mm_mul_epu32(a13,b13);__m128i prod01=_mm_unpacklo_epi32(prod02,prod13);__m128i prod23=_mm_unpackhi_epi32(prod02,prod13);__m128i prod=_mm_unpackhi_epi64(prod01,prod23);return prod;}void ntt(u32*__restrict__ x,int bit){int n=1<<bit,t=n;prep(n);for(int m=1;m<n;m<<=1){t>>=1;u32*__restrict__ p=p0[m];u32*__restrict__ q=q0[m];if(t==1){u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)for(int j=0;j<t;++j){u32 u=xa[j]-(xa[j]>=modm2)*modm2;u32 v=my_mul(xb[j],p[i],q[i]);xa[j]=u+v;xb[j]=u-v+modm2;}}else if(t==2){u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)for(int j=0;j<t;++j){u32 u=xa[j]-(xa[j]>=modm2)*modm2;u32 v=my_mul(xb[j],p[i],q[i]);xa[j]=u+v;xb[j]=u-v+modm2;}}else if(t==4){u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t){const __m128i p4=_mm_set1_epi32(p[i]),q4=_mm_set1_epi32(q[i]),mm=_mm_set1_epi32(mod+mod),m0=_mm_set1_epi32(0),m1=_mm_set1_epi32(mod);for(int j=0;j<t;j+=4){__m128i u=_mm_loadu_si128((__m128i*)(xa+j));u=_mm_sub_epi32(u,_mm_and_si128(_mm_or_si128(_mm_cmpgt_epi32(u,mm),_mm_cmpgt_epi32(m0,u)),mm));__m128i v=_mm_loadu_si128((__m128i*)(xb+j));v=_mm_sub_epi32(my_mullo_epu32(v,p4),my_mullo_epu32(my_mulhi_epu32(v,q4),m1));_mm_storeu_si128((__m128i*)(xa+j),_mm_add_epi32(u,v));_mm_storeu_si128((__m128i*)(xb+j),_mm_add_epi32(_mm_sub_epi32(u,v),mm));}}}else{u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t){const __m128i p4=_mm_set1_epi32(p[i]),q4=_mm_set1_epi32(q[i]),mm=_mm_set1_epi32(mod+mod),m0=_mm_set1_epi32(0),m1=_mm_set1_epi32(mod);for(int j=0;j<t;j+=8){__m128i u0=_mm_loadu_si128((__m128i*)(xa+j));__m128i u1=_mm_loadu_si128((__m128i*)(xa+j+4));__m128i v0=_mm_loadu_si128((__m128i*)(xb+j));__m128i v1=_mm_loadu_si128((__m128i*)(xb+j+4));u0=_mm_sub_epi32(u0,_mm_and_si128(_mm_or_si128(_mm_cmpgt_epi32(u0,mm),_mm_cmpgt_epi32(m0,u0)),mm));u1=_mm_sub_epi32(u1,_mm_and_si128(_mm_or_si128(_mm_cmpgt_epi32(u1,mm),_mm_cmpgt_epi32(m0,u1)),mm));v0=_mm_sub_epi32(my_mullo_epu32(v0,p4),my_mullo_epu32(my_mulhi_epu32(v0,q4),m1));v1=_mm_sub_epi32(my_mullo_epu32(v1,p4),my_mullo_epu32(my_mulhi_epu32(v1,q4),m1));_mm_storeu_si128((__m128i*)(xa+j),_mm_add_epi32(u0,v0));_mm_storeu_si128((__m128i*)(xa+j+4),_mm_add_epi32(u1,v1));_mm_storeu_si128((__m128i*)(xb+j),_mm_add_epi32(_mm_sub_epi32(u0,v0),mm));_mm_storeu_si128((__m128i*)(xb+j+4),_mm_add_epi32(_mm_sub_epi32(u1,v1),mm));}}}}for(int i=0;i<n;++i)x[i]-=(x[i]>=modm2)*modm2,x[i]-=(x[i]>=u32(mod))*u32(mod);}void intt(u32*__restrict__ x,int bit){int n=1<<bit,t=1;prep(n);for(int m=(n>>1);m;m>>=1){u32*__restrict__ p=p1[m];u32*__restrict__ q=q1[m];if(t==1){u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)for(int j=0;j<t;++j){u32 u=xa[j],v=xb[j];xa[j]=u+v-(u+v>=modm2)*modm2;xb[j]=my_mul(u-v+modm2,p[i],q[i]);}}else if(t==2){u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t)for(int j=0;j<t;++j){u32 u=xa[j],v=xb[j];xa[j]=u+v-(u+v>=modm2)*modm2;xb[j]=my_mul(u-v+modm2,p[i],q[i]);}}else if(t==4){u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t){const __m128i p4=_mm_set1_epi32(p[i]),q4=_mm_set1_epi32(q[i]),mm=_mm_set1_epi32(mod+mod),m0=_mm_set1_epi32(0),m1=_mm_set1_epi32(mod);for(int j=0;j<t;j+=4){__m128i u=_mm_loadu_si128((__m128i*)(xa+j));__m128i v=_mm_loadu_si128((__m128i*)(xb+j));__m128i uv=_mm_add_epi32(u,v);_mm_storeu_si128((__m128i*)(xa+j),_mm_sub_epi32(uv,_mm_and_si128(_mm_or_si128(_mm_cmpgt_epi32(uv,mm),_mm_cmpgt_epi32(m0,uv)),mm)));uv=_mm_add_epi32(_mm_sub_epi32(u,v),mm);_mm_storeu_si128((__m128i*)(xb+j),_mm_sub_epi32(my_mullo_epu32(uv,p4),my_mullo_epu32(my_mulhi_epu32(uv,q4),m1)));}}}else{u32*xa=x,*xb=x+t;for(int i=0;i<m;++i,xa+=t+t,xb+=t+t){const __m128i p4=_mm_set1_epi32(p[i]),q4=_mm_set1_epi32(q[i]),mm=_mm_set1_epi32(mod+mod),m0=_mm_set1_epi32(0),m1=_mm_set1_epi32(mod);for(int j=0;j<t;j+=8){__m128i u0=_mm_loadu_si128((__m128i*)(xa+j));__m128i u1=_mm_loadu_si128((__m128i*)(xa+j+4));__m128i v0=_mm_loadu_si128((__m128i*)(xb+j));__m128i v1=_mm_loadu_si128((__m128i*)(xb+j+4));__m128i uv0=_mm_add_epi32(u0,v0);__m128i uv1=_mm_add_epi32(u1,v1);_mm_storeu_si128((__m128i*)(xa+j),_mm_sub_epi32(uv0,_mm_and_si128(_mm_or_si128(_mm_cmpgt_epi32(uv0,mm),_mm_cmpgt_epi32(m0,uv0)),mm)));_mm_storeu_si128((__m128i*)(xa+j+4),_mm_sub_epi32(uv1,_mm_and_si128(_mm_or_si128(_mm_cmpgt_epi32(uv1,mm),_mm_cmpgt_epi32(m0,uv1)),mm)));uv0=_mm_add_epi32(_mm_sub_epi32(u0,v0),mm);uv1=_mm_add_epi32(_mm_sub_epi32(u1,v1),mm);_mm_storeu_si128((__m128i*)(xb+j),_mm_sub_epi32(my_mullo_epu32(uv0,p4),my_mullo_epu32(my_mulhi_epu32(uv0,q4),m1)));_mm_storeu_si128((__m128i*)(xb+j+4),_mm_sub_epi32(my_mullo_epu32(uv1,p4),my_mullo_epu32(my_mulhi_epu32(uv1,q4),m1)));}}}t<<=1;}u32 rn=qp(n,mod-2);for(int i=0;i<n;++i)x[i]=x[i]*(ull)rn%mod;}}using fast_number_theory_transform::intt;using fast_number_theory_transform::ntt;
	struct poly{vu32 f;template<typename _Tp=size_t,typename _Tv=u32>poly(_Tp len=1,_Tv same_val=0):f(len,same_val){}poly(const vu32&_f):f(_f){}poly(const vi32&_f){f.resize(((int)_f.size()));for(int i=0;i<((int)_f.size());i++){f[i]=_f[i]+((_f[i]>>31)&mod);}}template<typename T>poly(initializer_list<T>_f):poly(vector<T>(_f)){}template<typename T>poly(T*__first,T*__last):poly(vector<typename iterator_traits<T>::value_type>(__first,__last)){}inline operator vu32()const{return f;}inline vu32::iterator begin(){return f.begin();}inline vu32::iterator end(){return f.end();}void swap(poly&_f){f.swap(_f.f);}inline int degree()const{return f.size()-1;}inline int size()const{return f.size();}inline poly&resize(int x){return f.resize(x),*this;}inline poly&redegree(int x){return f.resize(x+1),*this;}inline void clear(){f.resize(1),f[0]=0;}inline void shrink(){int ndeg=f.size()-1;while(ndeg>0&&f[ndeg]==0)ndeg--;f.resize(ndeg+1);}inline void rev(){reverse(f.begin(),f.end());}inline poly split(int n)const{return n<=0?poly(1,1):(n<(int)f.size()?poly(f.begin(),f.begin()+n+1):poly(*this).redegree(n));}inline u32&operator[](u32 x){return f[x];}inline u32 operator[](u32 x)const{return f[x];}inline u32 get(u32 x)const{return x<f.size()?f[x]:0;}friend istream&operator>>(istream&in,poly&x){for(int i=0;i<x.f.size();i++)in>>x.f[i];return in;}friend ostream&operator<<(ostream&out,const poly&x){out<<x.f[0];for(int i=1;i<x.f.size();i++)out<<' '<<x.f[i];return out;}inline u32*data(){return f.data();}inline const u32*data()const{return f.data();}inline poly&operator+=(const poly&a){f.resize(max(f.size(),a.f.size()));for(int i=0;i<a.f.size();i++)f[i]=f[i]+a.f[i]-(f[i]+a.f[i]>=mod)*mod;return*this;}inline poly&operator-=(const poly&a){f.resize(max(f.size(),a.f.size()));for(int i=0;i<a.f.size();i++)f[i]=f[i]-a.f[i]+(f[i]<a.f[i])*mod;return*this;}inline poly&operator+=(const u32&b){f[0]=f[0]+b-mod*(f[0]+b>=mod);return*this;}inline poly&operator-=(const u32&b){f[0]=f[0]-b+mod*(f[0]<b);return*this;}inline poly operator+(const poly&a)const{return(poly(*this)+=a);}inline poly operator-(const poly&a)const{return(poly(*this)-=a);}friend inline poly operator+(u32 a,const poly&b){return(poly(1,a)+=b);}friend inline poly operator-(u32 a,const poly&b){return(poly(1,a)-=b);}friend inline poly operator+(const poly&a,u32 b){return(poly(a)+=poly(1,b));}friend inline poly operator-(const poly&a,u32 b){return(poly(a)-=poly(1,b));}inline poly operator-()const{poly _f;_f.f.resize(f.size());for(int i=0;i<_f.f.size();i++)_f.f[i]=(f[i]!=0)*mod-f[i];return _f;}inline poly amp(int k)const{poly ret(size());for(int i=0;i*k<=degree();++i)ret[i*k]=f[i];return ret;}inline poly&operator*=(const poly&a){int n=degree(),m=a.degree();if(n<16||m<16){f.resize(n+m+1);for(int i=n+m;i>=0;i--){f[i]=1ll*f[i]*a.f[0]%mod;for(int j=max(1,i-n),j_up=min(m,i);j<=j_up;j++)f[i]=(f[i]+1ll*f[i-j]*a.f[j])%mod;}return*this;}vu32 _f(a.f);int bit=lg(n+m)+1;f.resize(1<<bit);_f.resize(1<<bit);ntt(f.data(),bit);ntt(_f.data(),bit);for(int i=0;i<(1<<bit);i++)f[i]=1ll*f[i]*_f[i]%mod;intt(f.data(),bit);f.resize(n+m+1);return*this;}inline poly operator*(const poly&a)const{return(poly(*this)*=a);}template<typename T>inline friend poly operator*(const poly&a,const T&b){poly ret(a);for(int i=0;i<ret.f.size();++i)ret[i]=1ll*ret[i]*b%mod;return ret;}template<typename T>inline friend poly operator*(const T&b,const poly&a){poly ret(a);for(int i=0;i<ret.f.size();++i)ret[i]=1ll*ret[i]*b%mod;return ret;}template<typename T>inline poly&operator*=(const T&b){for(int i=0;i<f.size();++i)f[i]=1ll*f[i]*b%mod;return*this;}inline poly&operator>>=(int x){return f.resize(f.size()+x),memmove(f.data()+x,f.data(),4*(f.size()-x)),memset(f.data(),0,4*x),*this;}inline poly operator>>(int x)const{return(poly(*this)>>=x);}inline poly&operator<<=(int x){return x>=f.size()?(clear(),*this):(memmove(f.data(),f.data()+x,4*(f.size()-x)),f.resize(f.size()-x),*this);}inline poly operator<<(int x)const{return(poly(*this)<<=x);}inline poly&shiftindexwith(int x){return x>=f.size()?(memset(f.data(),0,4*f.size()),*this):(memmove(f.data(),f.data()+x,4*(f.size()-x)),memset(f.data(),0,4*x),*this);}inline poly shiftindex(int x)const{return(poly(*this).shiftindexwith(x));}inline poly inv()const;inline poly quo(const poly&g)const;inline poly operator/(const poly&g){return f.size()==1?poly(1,qp(g[0],-1,f[0])):quo(g);}inline poly&quowith(const poly&g){return f.size()==1?(f[0]=qp(g[0],-1,f[0]),*this):(*this=quo(g));}inline poly deri()const{int n=degree();poly res;res.redegree(n-1);for(int i=1;i<=n;i++)res[i-1]=1ll*f[i]*i%mod;return res;}inline poly intg(u32 C=0)const{int n=degree();poly res(1,C);res.redegree(n+1);for(int i=0;i<=n;i++)res[i+1]=1ll*ginv(i+1)*f[i]%mod;return res;}inline poly pow(u32 x,u32 modphix=-1){if(modphix==-1)modphix=x;int n=size()-1;i64 empt=0;while(empt<=n and!f[empt])++empt;if(1ll*empt*x>n)return poly(size());poly res(size());for(int i=0;i<=n-empt;++i)res[i]=f[i+empt];int val_0=res[0],inv_0=qp(val_0,mod-2),pow_0=qp(val_0,modphix);for(int i=0;i<=n-empt;++i)res[i]=1ll*res[i]*inv_0%mod;res=(res.ln()*x).exp();empt*=x;for(int i=n;i>=empt;--i)res[i]=1ll*res[i-empt]*pow_0%mod;for(int i=empt-1;i>=0;--i)res[i]=0;return res;}inline poly ivsqrt()const{int nsize=f.size(),mxb=lg(f.size()-1)+1;vu32 a(1<<mxb),_f(f);_f.resize(1<<mxb);a[0]=qp(math::isqrt(f[0]),mod-2);for(int nb=0;nb<mxb;nb++){vu32 _a(a.begin(),a.begin()+(1<<nb)),_b(_f.begin(),_f.begin()+(2<<nb));_a.resize(4<<nb);_b.resize(4<<nb);ntt(_a.data(),nb+2);ntt(_b.data(),nb+2);for(int i=0;i<(4<<nb);i++)_a[i]=1ull*(mod-_a[i])*_a[i]%mod*_a[i]%mod*_b[i]%mod,_a[i]=(_a[i]+(_a[i]&1)*mod)>>1;intt(_a.data(),nb+2);memcpy(a.data()+(1<<nb),_a.data()+(1<<nb),4<<nb);}return a.resize(nsize),a;}inline poly sqrt()const{if(f.size()==1)return poly(1,math::isqrt(f[0]));if(f.size()==2&&f[0]==1)return poly(vector<int>{1,(int)(1ll*f[1]*(mod+1)/2%mod)});int nsize=f.size(),mxb=lg(nsize-1)+1;vu32 a(1<<mxb),_f(f),_b;_f.resize(1<<mxb);a[0]=qp(math::isqrt(f[0]),mod-2);for(int nb=0;nb<mxb-1;nb++){vu32 _a(a.begin(),a.begin()+(1<<nb));_b=vu32(_f.begin(),_f.begin()+(2<<nb));_a.resize(4<<nb);_b.resize(4<<nb);ntt(_a.data(),nb+2);ntt(_b.data(),nb+2);for(int i=0;i<(4<<nb);i++)_a[i]=1ull*(mod-_a[i])*_a[i]%mod*_a[i]%mod*_b[i]%mod,_a[i]=(_a[i]+(_a[i]&1)*mod)>>1;intt(_a.data(),nb+2);memcpy(a.data()+(1<<nb),_a.data()+(1<<nb),4<<nb);}ntt(a.data(),mxb);vu32 _a(a);for(int i=0;i<(1<<mxb);i++)a[i]=1ll*a[i]*_b[i]%mod;intt(a.data(),mxb),memset(a.data()+(1<<(mxb-1)),0,2<<mxb);vu32 g0(a);ntt(a.data(),mxb),ntt(_f.data(),mxb);for(int i=0;i<(1<<mxb);i++)a[i]=(1ll*a[i]*a[i]+mod-_f[i])%mod*(mod-_a[i])%mod,a[i]=(a[i]+(a[i]&1)*mod)>>1;intt(a.data(),mxb);memcpy(g0.data()+(1<<(mxb-1)),a.data()+(1<<(mxb-1)),2<<mxb);return g0;}inline poly czt(int c,int m)const{poly ret(f);int inv=qp(c,mod-2),n=ret.size();ret.resize(m);poly F(n),G(n+m);for(int i=0,p1=1,p2=1;i<n;++i){F[n-i-1]=1ll*ret[i]*p1%mod;i&&(p2=1ll*p2*inv%mod,p1=1ll*p1*p2%mod,true);}for(int i=0,p1=1,p2=1;i<n+m;++i){G[i]=p1;i&&(p2=1ll*p2*c%mod,p1=1ll*p1*p2%mod,true);}F=F*G;for(int i=0,p1=1,p2=1;i<m;++i){ret[i]=1ll*F[i+n-1]*p1%mod;i&&(p2=1ll*p2*inv%mod,p1=1ll*p1*p2%mod,true);}return ret;}inline poly ChirpZ(int c,int m)const{return czt(c,m);}inline poly shift(int c)const{c%=mod;c=c+(c<0)*mod;if(c==0)return*this;poly A(size()),B(size()),ret(size());for(int i=0;i<size();++i)A[size()-i-1]=1ll*f[i]*gfac(i)%mod;for(int i=0,pc=1;i<size();++i,pc=1ll*pc*c%mod)B[i]=1ll*pc*gifc(i)%mod;A*=B;A.resize(size());for(int i=0;i<size();++i)ret[i]=1ll*A[size()-i-1]*gifc(i)%mod;return ret;}inline poly fdt()const{poly F(*this),E(size());for(int i=0;i<size();++i)E[i]=gifc(i);F*=E;F.resize(size());for(int i=0;i<size();++i)F[i]=1ll*F[i]*gfac(i)%mod;return F;}inline poly ifdt()const{poly F(*this),E(size());for(int i=0;i<size();++i)F[i]=1ll*F[i]*gifc(i)%mod;for(int i=0;i<size();++i)if(i&1)E[i]=mod-gifc(i);else E[i]=gifc(i);return(F*E).split(degree());}inline poly ln()const;inline poly exp()const;inline poly eval(int n,poly a)const;inline poly intp(int n,const poly&x,const poly&y);inline poly sin()const{int omega_4=qp(proot,(mod-1)>>2);poly F=((*this)*omega_4).exp();return qp(omega_4*2,mod-2)*(F-F.inv());}inline poly cos()const{int omega_4=qp(proot,(mod-1)>>2);poly F=((*this)*omega_4).exp();return qp(2,mod-2)*(F+F.inv());}inline poly tan()const{return sin()/cos();}inline poly asin()const{poly A=deri(),B=(*this)*(*this);B.resize(size());B=(1-B).ivsqrt();return(A*B).intg().split(degree());}inline poly acos()const{poly A=(mod-1)*deri(),B=(*this)*(*this);B.resize(size());B=(1-B).ivsqrt();return(A*B).intg().split(degree());}inline poly atan()const{poly A=deri(),B=1+(*this)*(*this);B.resize(size());B=B.inv();return(A*B).intg().split(degree());}};inline poly operator""_p(const char*str,size_t len){poly ans(2);int sgn=1,phase=0,coeff=0,touch=0;i32 cnum=0;auto clean=[&](){if(sgn==-1)coeff=(coeff==0?coeff:mod-coeff);if(phase==-1)ans[1]+=coeff;else if(phase==0)ans[0]+=(int)cnum;else if(phase==1)ans.resize(max(cnum+1,ans.size())),ans[cnum]+=coeff;else assert(0);phase=cnum=touch=0;};for(int i=0;i<(int)len;++i){if(str[i]=='+')clean(),sgn=1;else if(str[i]=='-')clean(),sgn=-1;else if('0'<=str[i]and str[i]<='9'){assert(phase==0||phase==1);if(phase==0)touch=1,cnum=(10ll*cnum+str[i]-48)%mod;else cnum=10ll*cnum+str[i]-48,assert(cnum<1e8);}else if(str[i]=='x'){while(str[i+1]==' ')++i;assert(str[i+1]=='^'||str[i+1]=='+'||str[i+1]=='-'||str[i+1]==0);phase=-1;coeff=touch?cnum:1;cnum=0;}else if(str[i]=='^'){assert(phase==-1);phase=1;}}clean();return ans;}
	namespace __semiconvol__{const int logbr=4,br=1<<logbr,maxdep=(maxbit-1)/logbr+1,__bf=6,bf=max(__bf,logbr-1),pbf=1<<bf;inline void src(poly&f,const poly&g,const function<void(const int&,poly&,const poly&)>&relax){int nsize=g.size(),mxb=lg(nsize-1)+1;math::basic_math::__prep(mxb);f.resize(1<<mxb);vu32 __prentt[maxdep][br];for(int i=0,k=mxb;k>bf;k-=logbr,i++){for(int j=0;j<br-1;j++){if((j<<(k-logbr))>=nsize)break;__prentt[i][j].resize(2<<(k-logbr));int nl=(j<<(k-logbr)),nr=min(((j+2)<<(k-logbr)),nsize)-nl;memcpy(__prentt[i][j].data(),g.data()+nl,nr*4);ntt(__prentt[i][j].data(),k-logbr+1);}}function<void(int,int,int)>__div=[&f,&__prentt,&g,&mxb,&__div,&relax](int x,int l,int r){if(r-l<=pbf){for(int i=l;i<r;i++){relax(i,f,g);if(i+1<r)for(int j=i+1;j<r;j++)f[j]=(f[j]+1ll*f[i]*g[j-i])%mod;}return;}int nbit=mxb-logbr*(x+1),nbr=0;vu32 __tmp[br];while(l+(nbr<<nbit)<r){__tmp[nbr].resize(2<<nbit);nbr++;}for(int i=0;i<nbr;i++){if(i!=0){intt(__tmp[i].data(),nbit+1);for(int j=0;j<(1<<nbit);j++){u32&x=f[l+(i<<nbit)+j],&y=__tmp[i][j+(1<<nbit)];x=x+y-(x+y>=mod)*mod,y=0;}}__div(x+1,l+(i<<nbit),min(l+((i+1)<<nbit),r));if(i!=nbr-1){memcpy(__tmp[i].data(),f.data()+l+(i<<nbit),4<<nbit);ntt(__tmp[i].data(),nbit+1);for(int j=i+1;j<nbr;j++)for(int k=0;k<(2<<nbit);k++)__tmp[j][k]=(__tmp[j][k]+1ll*__tmp[i][k]*__prentt[x][j-i-1][k])%mod;}}};__div(0,0,nsize);f.resize(nsize);}}using __semiconvol__::src;inline poly poly::ln()const{poly ret;src(ret,*this,[&](const int&i,poly&f,const poly&g){if(i==0)f[i]=0;else f[i]=(1ll*g[i]*i+mod-f[i])%mod;});pre(i,degree(),1)ret[i]=1ll*ginv(i)*ret[i]%mod;return ret;}inline poly poly::exp()const{poly ret,tmp(*this);rep(i,0,degree())tmp[i]=1ll*tmp[i]*i%mod;src(ret,tmp,[&](const int&i,poly&f,const poly&g){if(i==0)f[i]=1;else f[i]=1ll*f[i]*ginv(i)%mod;});return ret;}inline poly poly::inv()const{poly ret,tmp(*this);int ivf0=qp(f[0],mod-2);tmp[0]=0;src(ret,tmp,[&](const int&i,poly&f,const poly&g){if(i==0)f[i]=ivf0;else f[i]=1ll*ivf0*(mod-f[i])%mod;});return ret;}inline poly poly::quo(const poly&g)const{using namespace __semiconvol__;int nsize=f.size(),mxb=lg(nsize-1)+1;vu32 res(1<<mxb),__prentt[maxdep][br],_f(g.f);u32 ivf0=qp(_f[0],-1);_f[0]=0;_f.resize(nsize);for(int i=0,k=mxb;k>bf;k-=logbr,i++){for(int j=0;j<br-1;j++){if((j<<(k-logbr))>=nsize)break;__prentt[i][j].resize(2<<(k-logbr));int nl=(j<<(k-logbr)),nr=min(((j+2)<<(k-logbr)),nsize)-nl;memcpy(__prentt[i][j].data(),_f.data()+nl,nr*4);ntt(__prentt[i][j].data(),k-logbr+1);}}function<void(int,int,int)>__div=[=,&res,&__prentt,&_f,&mxb,&__div,&ivf0](int x,int l,int r){if(r-l<=pbf){for(int i=l;i<r;i++){res[i]=1ll*ivf0*(i==0?f[0]:f[i]+mod-res[i])%mod;if(i+1<r){u64 __tmp=res[i];for(int j=i+1;j<r;j++)res[j]=(res[j]+__tmp*_f[j-i])%mod;}}return;}int nbit=mxb-logbr*(x+1),nbr=0;vu32 __tmp[br];while(l+(nbr<<nbit)<r){__tmp[nbr].resize(2<<nbit);nbr++;}for(int i=0;i<nbr;i++){if(i!=0){intt(__tmp[i].data(),nbit+1);for(int j=0;j<(1<<nbit);j++){u32&x=res[l+(i<<nbit)+j],&y=__tmp[i][j+(1<<nbit)];x=x+y-(x+y>=mod)*mod,y=0;}}__div(x+1,l+(i<<nbit),min(l+((i+1)<<nbit),r));if(i!=nbr-1){memcpy(__tmp[i].data(),res.data()+l+(i<<nbit),4<<nbit);ntt(__tmp[i].data(),nbit+1);for(int j=i+1;j<nbr;j++)for(int k=0;k<(2<<nbit);k++)__tmp[j][k]=(__tmp[j][k]+1ll*__tmp[i][k]*__prentt[x][j-i-1][k])%mod;}}};__div(0,0,nsize);return res.resize(nsize),res;}
	namespace __multipoint_operation__{vector<poly>__Q;poly _E_Mul(poly A,poly B){int n=A.size(),m=B.size();B.rev();B=A*B;for(int i=0;i<n;++i)A[i]=B[i+m-1];return A;}void _E_Init(int p,int l,int r,poly&a){if(l==r){__Q[p].resize(2);__Q[p][0]=1,__Q[p][1]=(a[l]?mod-a[l]:a[l]);return;}int mid=l+r>>1;_E_Init(p<<1,l,mid,a),_E_Init(p<<1|1,mid+1,r,a);__Q[p]=__Q[p<<1]*__Q[p<<1|1];}void _E_Calc(int p,int l,int r,const poly&F,poly&g){if(l==r)return void(g[l]=F[0]);poly __F(r-l+1);for(int i=0,ed=r-l+1;i<ed;++i)__F[i]=F[i];int mid=l+r>>1;_E_Calc(p<<1,l,mid,_E_Mul(__F,__Q[p<<1|1]),g);_E_Calc(p<<1|1,mid+1,r,_E_Mul(__F,__Q[p<<1]),g);}vector<poly>__P;void _I_Init(int p,int l,int r,const poly&x){if(l==r){__P[p].resize(2),__P[p][0]=(x[l]?mod-x[l]:0),__P[p][1]=1;return;}int mid=l+r>>1;_I_Init(p<<1,l,mid,x),_I_Init(p<<1|1,mid+1,r,x);__P[p]=__P[p<<1]*__P[p<<1|1];}poly _I_Calc(int p,int l,int r,const poly&t){if(l==r)return poly(1,t[l]);int mid=l+r>>1;poly L(_I_Calc(p<<1,l,mid,t)),R(_I_Calc(p<<1|1,mid+1,r,t));L=L*__P[p<<1|1],R=R*__P[p<<1];for(int i=0;i<(int)R.size();++i){L[i]=L[i]+R[i];if(L[i]>=mod)L[i]-=mod;}return L;}}inline poly poly::eval(int n,poly a)const{using namespace __multipoint_operation__;n=max(n,size());poly v(n),F(f);__Q.resize(n<<2);F.resize(n+1),a.resize(n);_E_Init(1,0,n-1,a);__Q[1].resize(n+1);_E_Calc(1,0,n-1,_E_Mul(F,__Q[1].inv()),v);return v;}inline poly poly::intp(int n,const poly&x,const poly&y){using namespace __multipoint_operation__;__P.resize(n<<2);_I_Init(1,0,n-1,x);__P[1]=__P[1].deri();poly t=__P[1].eval(n,x);for(int i=0;i<n;++i)t[i]=1ll*y[i]*qp(t[i],mod-2)%mod;f=_I_Calc(1,0,n-1,t);return*this;}}using math::gfac;using math::gifc;using math::ginv;using math::qp;using math::basic_math::gC;using namespace polynomial;
	namespace plugins{using math::gfac;using math::gifc;using math::ginv;using math::qp;using polynomial::poly;poly _S1R_solve(const int&n){if(n==0)return poly(1,1);int mid=n>>1;poly f=_S1R_solve(mid);f.resize(mid+1);poly A=f.shift(mid),B(mid+1);for(register int i=0;i<=mid;++i)B[i]=f[i];A*=B,f.resize(n+1);if(n&1)for(register int i=0;i<=n;++i)f[i]=((i?A[i-1]:0)+1ll*(n-1)*A[i])%mod;else for(register int i=0;i<=n;++i)f[i]=A[i];return f;}inline poly stirling2_row(const int&n){poly A(n+1),B(n+1);for(register int i=0;i<=n;i++)A[i]=(i&1?mod-gifc(i):gifc(i)),B[i]=1ll*qp(i,n)*gifc(i)%mod;return(A*B).split(n);}inline poly stirling2_col(const int&n,const int&k){poly f(n+1);rep(i,1,n)f[i]=gifc(i);f=f.pow(k);rep(i,0,n)f[i]=1ll*f[i]*gfac(i)%mod*gifc(k)%mod;return f;}inline poly stirling1_row(const int&n){return _S1R_solve(n);}inline poly stirling1_col(const int&n,const int&k){poly f(n+1);f[0]=1,f[1]=mod-1;f=f.inv().ln().pow(k);rep(i,0,n)f[i]=1ll*f[i]*gfac(i)%mod*gifc(k)%mod;return f;}inline poly SEQ(const poly&A){return(1-A).inv();}inline poly Q(const poly&A){return SEQ(A);}inline poly MSET(const poly&A){poly ret(A);for(register int i=2;i<A.size();++i)for(register int j=1;i*j<A.size();++j)ret[i*j]=(ret[i*j]+1ll*ginv(i)*A[j])%mod;return ret.exp();}inline poly Exp(const poly&A){return MSET(A);}inline poly Ln(poly f){f[0]=1;f=f.ln();for(register int i=1;i<f.size();++i)f[i]=1ll*f[i]*i%mod;poly prime(f.size()+1),mu(f.size()+1),ret(f.size());vector<bool>vis(f.size()+1);int cnt=0;mu[1]=1;for(register int i=2;i<=f.size();++i){if(!vis[i])prime[++cnt]=i,mu[i]=mod-1;for(register int j=1;j<=cnt and i*prime[j]<=f.size();++j){vis[i*prime[j]]=1;if(i%prime[j]==0)break;mu[i*prime[j]]=(mu[i]==0?0:mod-mu[i]);}}for(register int i=1;i<f.size();++i)for(register int j=1;i*j<f.size();++j)ret[i*j]=(ret[i*j]+1ll*f[i]*mu[j])%mod;for(register int i=1;i<ret.size();++i)if(ret[i])ret[i]=1ll*ret[i]*ginv(i)%mod;ret[0]=0;return ret;}inline int _R_Div(poly F,poly G,ll n){using namespace polynomial::fast_number_theory_transform;int len=max(F.size(),G.size());int m=1,o=0;while(m<len)m<<=1,++o;F.resize(1<<o+1),G.resize(1<<o+1);while(n>m){ntt(F.data(),o+1),ntt(G.data(),o+1);for(register int i=0;i<m*2;++i)F[i]=1ll*F[i]*G[i^1]%mod;for(register int i=0;i<m;++i)G[i]=1ll*G[i<<1]*G[i<<1|1]%mod;intt(F.data(),o+1);intt(G.data(),o);for(register int i=0,j=n&1;i<len;i++,j+=2)F[i]=F[j];for(register int i=len,ed=1<<o+1;i<ed;++i)F[i]=G[i]=0;n>>=1;}G.resize(m);G=G.inv();int s=n;n=F.size()-1,m=G.size()-1;int a=max(0,s-m),b=min(s,n),ans=0;for(register int i=a;i<=b;++i)ans=(ans+1ll*F[i]*G[s-i])%mod;return ans;}inline int linear_recur(ll n,int k,poly f,poly a){poly F(k+1);F[k]=1;assert(a.size()>=k);a.resize(k);for(register int i=1;i<=k;++i)assert(0<=f[i]and f[i]<mod),F[k-i]=(f[i]==0?0:mod-f[i]);F.rev();f=(a*F).split(a.degree());return _R_Div(f,F,n);}inline poly BM(int n,poly a){a.f.emplace(a.f.begin(),0);poly ans,lst;i32 w=0;ll delt=0;for(register int i=1;i<=n;++i){ll tmp=0;for(register int j=0;j<ans.size();++j)tmp=(tmp+1ll*a[i-j-1]*ans[j])%mod;if((a[i]-tmp+mod)%mod==0)continue;if(!w){w=i,delt=a[i]-tmp+mod;if(delt>=mod)delt-=mod;for(register int j=i;j;--j)ans.f.emplace_back(0);continue;}poly now=ans;ll mult=1ll*(a[i]-tmp+mod)*qp(delt,mod-2)%mod;if(ans.size()<lst.size()+i-w)ans.resize(lst.size()+i-w);ans[i-w-1]+=mult;if(ans[i-w-1]>=mod)ans[i-w-1]-=mod;for(register int j=0;j<lst.size();++j)ans[i-w+j]=(ans[i-w+j]-1ll*mult*lst[j]%mod+mod)%mod;if(now.size()-i<lst.size()-w)lst=now,w=i,delt=(a[i]-tmp+mod)%mod;}return ans;}inline int recur_by_bm(ll n,int k,poly a){poly f=BM(k,a);cout<<f<<'\n';if(f.size()==1)return 1ll*a[0]*qp(f[0],n-1)%mod;f.f.emplace(f.f.begin(),0);return linear_recur(n,f.degree(),f,a);}}using namespace plugins;
} using namespace __POLY__;

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
    poly f(n + 1), g(m + 1);
    rep(i,0,n) f[i] = a[i];
    rep(i,0,m) g[i] = b[i];
    f *= g;
    rep(i,0,f.degree()) c[i] = f[i];
}

评测结果