Polyard–Rho
考虑一个判定因数的方式。
你假设你需要判定集合
你考虑求出
此时如果
考虑分块。
令。
用分治的乘积结构来构造这个多项式，然后多项式求点值求出。
需要注意的是。
对于每一个块，计算出
复杂度是
对于 P1075
然后考虑三种情况。
由于最小质因子满足
:::success[AC code]
//Author:kevinZ99
#ifndef KEVIN_POLY_ALL_HPP
#define KEVIN_POLY_ALL_HPP
#include <bits/stdc++.h>
#define zr return
#define zs static
#define zc const
#define zt template
#define zy typename
#define zd typedef
#define zf friend
zt<class T>using V=std::vector<T>;zt<class A,class B>using Q=std::pair<A,B>;using S=std::size_t;using u32=uint32_t;using u64=uint64_t;using u128=__uint128_t;using i128=__int128_t;
#ifndef PI
#define PI inline __attribute__((always_inline))
#endif
namespace pd{
zt<class T>struct SE:std::is_signed<T>{};zt<>struct SE<i128>:std::true_type{};zt<>struct SE<u128>:std::false_type{};PI u64 M64(u64 a,u64 b,u64 m){zr(u128)a*b%m;}PI u64 I64(u64 a,u64 m){
if(m==0){
assert(a&1);u64 x=a;for(int i=0;i<6;i++)x*=2-a*x;zr x;}i128 t=0,nt=1;u64 r=m,nr=a%m;while(nr){u64 q=r/nr,rr=r-q*nr;r=nr;nr=rr;i128 tt=t-(i128)q*nt;t=nt;nt=tt;}assert(r==1);if(t<0)t+=m;zr(u64)t;}zt<u64 MOD> struct CT{zd zy std::conditional<(MOD!=0 && MOD<=0xffffffffULL),u32,u64>::type type;};zt<u64 MOD> struct MO{
zd zy CT<MOD>::type T;zt<class U> zs PI T norm(U x){zr norm_impl(x,zy SE<U>::type());}zt<class U> zs PI T norm_impl(U x,std::true_type){
if(MOD==0)zr(T)(u64)x;i128 y=(i128)x%(i128)MOD;if(y<0)y+=MOD;zr(T)y;}zt<class U> zs PI T norm_impl(U x,std::false_type){zr MOD?(T)((u128)x%MOD):(T)(u64)x;}zs PI T add(T a,T b){
if(MOD==0)zr(T)(a+b);if(MOD<=0xffffffffULL){u64 s=(u64)a+b;if(s>=MOD)s-=MOD;zr(T)s;}u64 s=a+b;if(s<a || s>=MOD)s-=MOD;zr s;}zs PI T sub(T a,T b){if(MOD==0)zr(T)(a-b);zr a>=b?a-b:(T)(MOD-(u64)b+a);}zs PI T neg(T a){zr a?(MOD?T(MOD-a):T(0-a)):0;}zs PI T mul(T a,T b){if(MOD==0)zr(T)(a*b);if(MOD<=0xffffffffULL)zr(T)((u64)a*b%MOD);zr(T)((u128)a*b%MOD);}zs PI T inv(T a){zr(T)I64((u64)a,MOD);}zs PI T pw(T a,u64 e){T r=norm(1);for(;e;e>>=1,a=mul(a,a))if(e&1)r=mul(r,a);zr r;}};
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
#include <immintrin.h>
using X=__m256i;
#define PA __attribute__((target("avx2")))
#define PVL(x) _mm256_loadu_si256((const X*)(x))
#define PVS(x,v) _mm256_storeu_si256((X*)(x),v)
#define V0 _mm256_sub_epi32
#define V1 _mm256_add_epi32
#define V2 _mm256_setr_epi32
#define V3 _mm256_mul_epu32
#define V4 _mm256_blend_epi32
#define V5 _mm256_shuffle_epi32
#define V6 _mm256_set1_epi32
#define V7 _mm256_permutevar8x32_epi32
#define V8 _mm256_min_epu32
#define V9 _mm256_srli_epi64
#define VA _mm256_set1_epi64x
#define VB _mm256_permute4x64_epi64
#define VC _mm256_add_epi64
#define VD _mm256_set_epi64x
#define VE _mm256_permute2x128_si256
#define VF _mm256_or_si256
#define VG _mm256_srli_si256
#define VH _mm256_slli_epi64
zt<u32 P,u32 G>struct AN{
zs PI u32 sm(u32 a,u32 b){zr(u64)a*b%P;}zs u32 pw(u32 a,u32 e){u32 x=1;for(;e;e>>=1,a=sm(a,a))if(e&1)x=sm(x,a);zr x;}zs u32 ni32(){u32 x=1;for(int i=0;i<5;i++)x*=2-P*x;zr 0u-x;}
struct R{u32 ni,r,r2,w[4],wr[4];u64 wd[30][4],wid[30][4];u32 wl[30][8],wil[30][8];R(){ni=ni32();r=(u64(1)<<32)%P;r2=(u64)r*r%P;int l=__builtin_ctz(P-1);u32 x[31]={},y[31]={};x[l]=tm(pw(G,(P-1)>>l));y[l]=tm(pw(pw(G,(P-1)>>l),P-2));for(int i=l-1;i>=0;i--)x[i]=mm(x[i+1],x[i+1]),y[i]=mm(y[i+1],y[i+1]);w[0]=wr[0]=r;if(l>=2){w[1]=x[2];wr[1]=y[2];if(l>=3)w[2]=x[3],wr[2]=y[3],w[3]=mm(w[1],w[2]),wr[3]=mm(wr[1],wr[2]);}u32 a=r,b=r;for(int i=0;i<l-2;i++){u32 f=mm(a,x[i+3]),g=mm(b,y[i+3]);a=mm(a,y[i+3]);b=mm(b,x[i+3]);u32 f2=mm(f,f),g2=mm(g,g);u64 A[4]={f2,f,f2,f},B[4]={g2,g,g2,g};memcpy(wd[i],A,32);memcpy(wid[i],B,32);}a=b=r;for(int i=0;i<l-3;i++){u32 f=mm(a,x[i+4]),g=mm(b,y[i+4]);a=mm(a,y[i+4]);b=mm(b,x[i+4]);u32 f2=mm(f,f),f3=mm(f2,f2),g2=mm(g,g),g3=mm(g2,g2);u32 A[8]={f,f,f,f,f2,f2,f3,r},B[8]={g,g,g,g,g2,g2,g3,r};memcpy(wl[i],A,32);memcpy(wil[i],B,32);}}u32 rd(u64 x)zc{u32 m=(u32)x*ni,v=(u32)((x+(u64)m*P)>>32);zr v>=P?v-P:v;}u32 mm(u32 a,u32 b)zc{zr rd((u64)a*b);}u32 tm(u32 x)zc{zr mm(x,r2);}};
zs R&rr(){zs R x;zr x;}PA zs X ld(zc u32*x){zr PVL(x);}PA zs void st(u32*x,X v){PVS(x,v);}PA zs X sh(X x){X p=V6(P);zr V8(x,V0(x,p));}PA zs X ad(X a,X b){zr sh(V1(a,b));}PA zs X su(X a,X b){X d=V0(a,b);zr V8(d,V1(d,V6(P)));}
PA zs X mv(X a,X b,bool strict=true){R&q=rr();X ni=VA((u64)q.ni),p=VA(P),e=V3(a,b),o=V3(V9(a,32),V9(b,32));e=V9(VC(e,V3(V3(e,ni),p)),32);o=V9(VC(o,V3(V3(o,ni),p)),32);X z=VF(e,VH(o,32));zr strict?sh(z):z;}
PA zs X me(X a,X b,bool strict=true){R&q=rr();X ni=VA((u64)q.ni),p=VA(P),as=VG(a,4),e=V3(a,b),o=V3(as,b);e=VC(e,V3(V3(e,ni),p));o=VC(o,V3(V3(o,ni),p));X z=VF(VG(e,4),o);zr strict?sh(z):z;}
PA zs X h2(X x){X m=V6(P*2);zr V8(x,V0(x,m));}PA zs void hb(X a,X t,X&x,X&y){a=h2(a);x=V1(a,t);y=V0(V1(a,V6(P*2)),t);}PA zs void hi(X a,X b,X&x,X&y){a=h2(a);b=h2(b);x=V1(a,b);y=V0(V1(a,V6(P*2)),b);}zt<bool I,bool T>PA zs void b4(u32*a,u32*b,u32*c,u32*d,X w1,X w2,X w3){X A=sh(h2(ld(a))),B=sh(h2(ld(b))),C=sh(h2(ld(c))),D=sh(h2(ld(d)));if(!I){if(!T)C=mv(C,w1,false);{X x,y;hb(A,C,x,y);A=x;C=y;}if(!T)D=mv(D,w1,false);{X x,y;hb(B,D,x,y);B=x;D=y;}if(!T)B=me(B,w2,false);{X x,y;hb(A,B,x,y);A=x;B=y;}D=me(D,w3,false);{X x,y;hb(C,D,x,y);C=x;D=y;}}else{{X x,y;hi(A,B,x,y);if(!T)y=me(y,w2,false);A=x;B=y;}{X x,y;hi(C,D,x,y);y=me(y,w3,false);C=x;D=y;}{X x,y;hi(A,C,x,y);if(!T)y=mv(y,w1,false);A=x;C=y;}{X x,y;hi(B,D,x,y);if(!T)y=mv(y,w1,false);B=x;D=y;}}st(a,A);st(b,B);st(c,C);st(d,D);}
zt<bool I,bool T>PA zs void ax(int k,int o,u32*d,X&w){X w1=V5(w,0),w2=VB(w,0x55),w3=VB(w,0xff);int q=1<<k;for(int j=0;j<q;j+=8)b4<I,T>(d+o+j,d+o+q+j,d+o+2*q+j,d+o+3*q+j,w1,w2,w3);int z=__builtin_ctz(~(u32)o>>(k+2));w=mv(w,ld((u32*)(I?rr().wid[z]:rr().wd[z])));}
PA zs void lo(u32*d,X w0,X w1,X w2,X M){X v=ld(d);v=mv(v,w0,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w1,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w2,false);X x=V1(V4(v,V0(M,v),0xaa),V5(v,0xb1));st(d,V8(x,V0(x,M)));}
zt<bool T>PA zs void ax2(int k,int o,u32*a,u32*b,X&w){X w1=V5(w,0),w2=VB(w,0x55),w3=VB(w,0xff);int q=1<<k;for(int j=0;j<q;j+=8){b4<0,T>(a+o+j,a+o+q+j,a+o+2*q+j,a+o+3*q+j,w1,w2,w3);b4<0,T>(b+o+j,b+o+q+j,b+o+2*q+j,b+o+3*q+j,w1,w2,w3);}int z=__builtin_ctz(~(u32)o>>(k+2));w=mv(w,ld((u32*)rr().wd[z]));}
PA zs void fw2(int l,u32*a,u32*b){R&q=rr();if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(ld(a+j)),B=sh(ld(a+s+j)),C=sh(ld(b+j)),D=sh(ld(b+s+j));st(a+j,ad(A,B));st(a+s+j,su(A,B));st(b+j,ad(C,D));st(b+s+j,su(C,D));}}for(int k=l-2-(!(l&1));k>=3;k-=2){X w=VD(q.w[1],q.w[0],q.w[0],q.w[0]);ax2<1>(k,0,a,b,w);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax2<0>(k,i,a,b,w);}X w=V2(q.w[0],q.w[1],q.w[2],q.w[3],q.w[0],q.w[1],q.w[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C);lo(a+i,w0,w1,w2,M);lo(b+i,w0,w1,w2,M);if(i+8<(1<<l))w=mv(w,ld(q.wl[__builtin_ctz(~(u32)i>>3)]));}}
PA zs void fw(int l,u32*d){R&q=rr();if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(ld(d+j)),B=sh(ld(d+s+j));st(d+j,ad(A,B));st(d+s+j,su(A,B));}}for(int k=l-2-(!(l&1));k>=3;k-=2){X w=VD(q.w[1],q.w[0],q.w[0],q.w[0]);ax<0,1>(k,0,d,w);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax<0,0>(k,i,d,w);}X w=V2(q.w[0],q.w[1],q.w[2],q.w[3],q.w[0],q.w[1],q.w[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C),v=ld(d+i);v=mv(v,w0,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w1,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w2,false);v=V8(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),V0(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),M));st(d+i,v);if(i+8<(1<<l))w=mv(w,ld(q.wl[__builtin_ctz(~(u32)i>>3)]));}}
PA zs void iv(int l,u32*d,u32 ex=0){R&q=rr();X w=V2(q.wr[0],q.wr[1],q.wr[2],q.wr[3],q.wr[0],q.wr[1],q.wr[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C),v=ld(d+i);v=mv(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),w2,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w1,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w0,false);st(d+i,v);if(i+8<(1<<l))w=mv(w,ld(q.wil[__builtin_ctz(~(u32)i>>3)]));}for(int k=3;k+2<=l;k+=2){X z=VD(q.wr[1],q.wr[0],q.wr[0],q.wr[0]);ax<1,1>(k,0,d,z);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax<1,0>(k,i,d,z);}if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(h2(ld(d+j))),B=sh(h2(ld(d+s+j)));st(d+j,ad(A,B));st(d+s+j,su(A,B));}}u32 f=sm(pw(1u<<l,P-2),q.r);if(ex)f=sm(f,ex);X F=V6(f);for(int i=0;i<(1<<l);i+=8)st(d+i,mv(ld(d+i),F));}
zt<bool N,class A,class B>PA zs V<u32> conv(zc A&a,zc B&b){int z=1,n=(int)a.size()+(int)b.size()-1;while(z<n)z<<=1;V<u32>x(z),y(z);for(S i=0;i<a.size();i++)x[i]=N?(u32)a[i]:(u32)((u64)a[i]%P);for(S i=0;i<b.size();i++)y[i]=N?(u32)b[i]:(u32)((u64)b[i]%P);int l=__builtin_ctz((u32)z);fw2(l,x.data(),y.data());for(int i=0;i<z;i+=8)st(x.data()+i,mv(ld(x.data()+i),ld(y.data()+i),false));iv(l,x.data(),rr().r);x.resize(n);for(u32&v:x)if(v>=P)v-=P;zr x;}
zt<bool N,class A>PA zs V<u32> square(zc A&a){int z=1,n=(int)a.size()*2-1;while(z<n)z<<=1;V<u32>x(z);for(S i=0;i<a.size();i++)x[i]=N?(u32)a[i]:(u32)((u64)a[i]%P);int l=__builtin_ctz((u32)z);fw(l,x.data());for(int i=0;i<z;i+=8){X X=ld(x.data()+i);st(x.data()+i,mv(X,X,false));}iv(l,x.data(),rr().r);x.resize(n);for(u32&v:x)if(v>=P)v-=P;zr x;}
PA zs void normal_ntt(V<u32>&a,bool I){int l=__builtin_ctz((u32)a.size());if(I)iv(l,a.data());else fw(l,a.data());for(u32&v:a)if(v>=P)v-=P;}
PA zs void invext(zc V<u32>&f,V<u32>&g,S z){S m=g.size(),L=m<<1;V<u32>F(L),Q(L),E(L);for(S i=0;i<std::min(f.size(),L);i++)F[i]=f[i];for(S i=0;i<m;i++)Q[i]=g[i];int l=__builtin_ctz((u32)L);fw2(l,F.data(),Q.data());for(S i=0;i<L;i+=8)st(F.data()+i,mv(ld(F.data()+i),ld(Q.data()+i),false));iv(l,F.data(),rr().r);for(S i=0;i<m;i++)E[i]=F[m+i];fw(l,E.data());for(S i=0;i<L;i+=8)st(E.data()+i,mv(ld(E.data()+i),ld(Q.data()+i),false));iv(l,E.data(),rr().r);g.resize(z);for(S i=m;i<z;i++){u32 x=E[i-m];if(x>=P)x-=P;g[i]=x?P-x:0;}}
PA zs V<V<u32> > cross(zc V<u32>&al,zc V<u32>&ah,zc V<u32>&bl,zc V<u32>&bh,bool hh){int n=(int)al.size()+(int)bl.size()-1,z=1;while(z<n)z<<=1;V<u32>A(z),H(z),B(z),K(z),t(z);for(S i=0;i<al.size();i++)A[i]=al[i]%P,H[i]=ah[i]%P;for(S i=0;i<bl.size();i++)B[i]=bl[i]%P,K[i]=bh[i]%P;int l=__builtin_ctz((u32)z);fw2(l,A.data(),H.data());fw2(l,B.data(),K.data());V<V<u32> >r(hh?3:2,V<u32>(n));for(int c=0;c<(hh?3:2);c++){for(int i=0;i<z;i+=8){X x=c==0?mv(ld(A.data()+i),ld(B.data()+i),false):c==1?ad(mv(ld(A.data()+i),ld(K.data()+i)),mv(ld(H.data()+i),ld(B.data()+i))):mv(ld(H.data()+i),ld(K.data()+i),false);st(t.data()+i,x);}iv(l,t.data(),rr().r);for(int i=0;i<n;i++)r[c][i]=t[i]>=P?t[i]-P:t[i];}zr r;}
};
#undef PVL
#undef PVS
#endif
zt<u32 P,u32 G> struct NTT{
zs PI u32 add(u32 a,u32 b){u32 s=a+b;zr s>=P?s-P:s;}zs PI u32 sub(u32 a,u32 b){zr a>=b?a-b:a+P-b;}zs PI u32 mul(u32 a,u32 b){zr(u64)a*b%P;}zs PI u32 normv(u64 a){zr(u32)(a%P);}zs u32 pw(u32 a,u32 e){u32 r=1;for(;e;e>>=1,a=mul(a,a))if(e&1)r=mul(r,a);zr r;}zs bool avx(){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
zs zc bool x=(P<(1u<<30))&&__builtin_cpu_supports("avx2");zr x;
#undef V0
#undef V1
#undef V2
#undef V3
#undef V4
#undef V5
#undef V6
#undef V7
#undef V8
#undef V9
#undef VA
#undef VB
#undef VC
#undef VD
#undef VE
#undef VF
#undef VG
#undef VH
#else
zr false;
#endif
}zs void ntt(V<u32>&a,bool iv){assert((P-1)%a.size()==0);if(a.size()<=1)zr;
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx()&&a.size()>=8){AN<P,G>::normal_ntt(a,iv);zr;}
#endif
int n=(int)a.size();for(int i=1,j=0;i<n;i++){int b=n>>1;for(;j&b;b>>=1)j^=b;j^=b;if(i<j)std::swap(a[i],a[j]);}for(int l=2;l<=n;l<<=1){u32 w=pw(G,(P-1)/l);if(iv)w=pw(w,P-2);for(int i=0;i<n;i+=l){u32 x=1;for(int j=0;j<(l>>1);j++,x=mul(x,w)){u32 u=a[i+j],v=mul(a[i+j+(l>>1)],x);a[i+j]=add(u,v);a[i+j+(l>>1)]=sub(u,v);}}}if(iv){u32 x=pw(n,P-2);for(u32&v:a)v=mul(v,x);}}zs bool invext(zc V<u32>&f,V<u32>&g,S z){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx()&&(g.size()<<1)>=8){AN<P,G>::invext(f,g,z);zr true;}
#endif
zr false;}zt<bool NORMAL,class A,class B> zs V<u32> cv(zc A&a,zc B&b){if(a.empty()||b.empty())zr{};if(std::min(a.size(),b.size())<=56){V<u32>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=(c[i+j]+(u64)(u32)a[i]*(u32)b[j])%P;zr c;}
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::zt conv<NORMAL>(a,b);
#endif
int z=1,need=(int)a.size()+(int)b.size()-1;while(z<need)z<<=1;V<u32>x(z),y(z);for(S i=0;i<a.size();i++)x[i]=NORMAL?(u32)a[i]:(u32)((u64)a[i]%P);for(S i=0;i<b.size();i++)y[i]=NORMAL?(u32)b[i]:(u32)((u64)b[i]%P);ntt(x,0);ntt(y,0);for(int i=0;i<z;i++)x[i]=mul(x[i],y[i]);ntt(x,1);x.resize(need);zr x;}zt<class A,class B> zs V<u32> conv(zc A&a,zc B&b){zr cv<false>(a,b);}zt<class A,class B> zs V<u32> conv_norm(zc A&a,zc B&b){zr cv<true>(a,b);}zt<class A> zs V<u32> square_norm(zc A&a){if(a.empty())zr{};if(a.size()<=56)zr cv<true>(a,a);
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::zt square<true>(a);
#endif
int z=1,need=(int)a.size()*2-1;while(z<need)z<<=1;V<u32>x(z);std::copy(a.begin(),a.end(),x.begin());ntt(x,0);for(int i=0;i<z;i++)x[i]=mul(x[i],x[i]);ntt(x,1);x.resize(need);zr x;}zs V<V<u32> > cross(zc V<u32>&al,zc V<u32>&ah,zc V<u32>&bl,zc V<u32>&bh,bool hh){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::cross(al,ah,bl,bh,hh);
#endif
int need=(int)al.size()+(int)bl.size()-1,z=1;while(z<need)z<<=1;V<u32>A(z),H(z),B(z),K(z),t(z);for(S i=0;i<al.size();i++)A[i]=al[i]%P,H[i]=ah[i]%P;for(S i=0;i<bl.size();i++)B[i]=bl[i]%P,K[i]=bh[i]%P;ntt(A,0);ntt(H,0);ntt(B,0);ntt(K,0);V<V<u32> >r(hh?3:2,V<u32>(need));for(int c=0;c<(hh?3:2);c++){for(int i=0;i<z;i++)t[i]=c==0?mul(A[i],B[i]):c==1?add(mul(A[i],K[i]),mul(H[i],B[i])):mul(H[i],K[i]);ntt(t,1);std::copy(t.begin(),t.begin()+need,r[c].begin());}zr r;}};using N1=NTT<998244353,3>;using N2=NTT<754974721,11>;using N3=NTT<469762049,3>;using N4=NTT<167772161,3>;using N5=NTT<1224736769,3>;zs zc u64 P1=998244353ULL,P2=754974721ULL,P3=469762049ULL;PI u128 crt3(u32 a,u32 b,u32 c){zs zc u64 i12=I64(P1%P2,P2),i123=I64((u128)P1*P2%P3,P3);u64 t2=(u64)((b+P2-a%P2)%P2)*i12%P2,x=(u64)a+P1*t2,t3=(u64)((c+P3-x%P3)%P3)*i123%P3;zr(u128)x+(u128)P1*P2*t3;}zt<u64 M> PI u32 crt3m(u32 a,u32 b,u32 c){zs zc u64 i12=I64(P1%P2,P2),i123=I64((u128)P1*P2%P3,P3),q1=P1%M,q12=q1*(P2%M)%M;u64 t2=(u64)((b+P2-a%P2)%P2)*i12%P2,x=(u64)a+P1*t2,t3=(u64)((c+P3-x%P3)%P3)*i123%P3,r=a%M;r=(r+q1*(t2%M)%M)%M;r=(r+q12*(t3%M)%M)%M;zr(u32)r;}zt<u64 MOD> struct DN{enum{yes=0};};zt<>struct DN<998244353ULL>{enum{yes=1};zd N1 N;};zt<>struct DN<754974721ULL>{enum{yes=1};zd N2 N;};zt<>struct DN<469762049ULL>{enum{yes=1};zd N3 N;};zt<>struct DN<167772161ULL>{enum{yes=1};zd N4 N;};zt<>struct DN<1224736769ULL>{enum{yes=1};zd N5 N;};zt<u64 MOD,bool DIRECT=DN<MOD>::yes> struct Conv;zt<u64 MOD>struct Conv<MOD,true>{zd zy CT<MOD>::type T;zs V<T>go(zc V<T>&a,zc V<T>&b){zd zy DN<MOD>::N N;zr N::conv_norm(a,b);}zs V<T>sq(zc V<T>&a){zd zy DN<MOD>::N N;zr N::square_norm(a);}};zt<u64 MOD>struct Conv<MOD,false>{zd zy CT<MOD>::type T;zs V<T>naive(zc V<T>&a,zc V<T>&b){V<T>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=MO<MOD>::add(c[i+j],MO<MOD>::mul(a[i],b[j]));zr c;}zs V<T>go32(zc V<T>&a,zc V<T>&b){auto x=N1::conv(a,b),y=N2::conv(a,b),z=N3::conv(a,b);V<T>c(x.size());for(S i=0;i<c.size();i++)c[i]=(T)crt3m<MOD>(x[i],y[i],z[i]);zr c;}zs V<T>go64(zc V<T>&a,zc V<T>&b){V<u32>al(a.size()),ah(a.size()),bl(b.size()),bh(b.size());for(S i=0;i<a.size();i++)al[i]=(u32)a[i],ah[i]=(u32)((u64)a[i]>>32);for(S i=0;i<b.size();i++)bl[i]=(u32)b[i],bh[i]=(u32)((u64)b[i]>>32);bool h=MOD!=0;auto r1=N1::cross(al,ah,bl,bh,h),r2=N2::cross(al,ah,bl,bh,h),r3=N3::cross(al,ah,bl,bh,h);V<T>c(r1[0].size());if(MOD==0){for(S i=0;i<c.size();i++){u64 lo=(u64)crt3(r1[0][i],r2[0][i],r3[0][i]),cr=(u64)crt3(r1[1][i],r2[1][i],r3[1][i]);c[i]=(T)(lo+(cr<<32));}}else{u64 r64=(u64)((u128(1)<<64)%MOD);for(S i=0;i<c.size();i++){u64 lo=(u64)(crt3(r1[0][i],r2[0][i],r3[0][i])%MOD),cr=(u64)(crt3(r1[1][i],r2[1][i],r3[1][i])%MOD),hi=(u64)(crt3(r1[2][i],r2[2][i],r3[2][i])%MOD),x=(u64)(((u128)lo+((u128)cr<<32))%MOD);c[i]=(T)MO<MOD>::add((T)x,(T)M64(hi,r64,MOD));}}zr c;}zs V<T>go(zc V<T>&a,zc V<T>&b){if(a.empty()||b.empty())zr{};if(std::min(a.size(),b.size())<=24)zr naive(a,b);zr go_dispatch(a,b,std::integral_constant<bool,(MOD!=0&&MOD<=0xffffffffULL)>());}zs V<T>sq(zc V<T>&a){zr go(a,a);}zs V<T>go_dispatch(zc V<T>&a,zc V<T>&b,std::true_type){zr go32(a,b);}zs V<T>go_dispatch(zc V<T>&a,zc V<T>&b,std::false_type){zr go64(a,b);}};}zt<u64 MOD> struct Poly{
zd zy pd::CT<MOD>::type T;zd pd::MO<MOD> O;V<T>a;Poly(){}Poly(S n):a(n){}Poly(zc V<T>&v):a(v){norm();}zt<class U> Poly(zc V<U>&v){a.resize(v.size());for(S i=0;i<v.size();i++)a[i]=O::norm(v[i]);norm();}zt<class U> Poly(std::initializer_list<U> v){a.reserve(v.size());for(auto x:v)a.push_back(O::norm(x));norm();}S size()zc{zr a.size();}bool empty()zc{zr a.empty();}int deg()zc{zr(int)a.size()-1;}T operator[](S i)zc{zr i<a.size()?a[i]:0;}T& operator[](S i){zr a[i];}zs T inv_int(S x){zr inv_int_dispatch(x,std::integral_constant<bool,pd::DN<MOD>::yes>());}zs T inv_int_dispatch(S x,std::false_type){zr O::inv(O::norm((u64)x));}zs T inv_int_dispatch(S x,std::true_type){assert(x&&x<MOD);zs V<T>v(2,1);v[0]=0;if(v.size()<=x){S o=v.size();v.resize(x+1);for(S i=o;i<=x;i++)v[i]=(T)(MOD-(u64)(MOD/i)*v[MOD%i]%MOD);}zr v[x];}void norm(){while(!a.empty()&&a.back()==0)a.pop_back();}Poly pre(S n)zc{if(a.size()<=n)zr *this;Poly r=*this;r.a.resize(n);r.norm();zr r;}Poly& cut(S n){if(a.size()>n)a.resize(n);norm();zr *this;}Poly rev(S n=0)zc{Poly r=*this;if(n)r.a.resize(n);std::reverse(r.a.begin(),r.a.end());r.norm();zr r;}zf Poly operator+(Poly x,zc Poly&y){zr x+=y;}zf Poly operator-(Poly x,zc Poly&y){zr x-=y;}zf Poly operator*(zc Poly&x,zc Poly&y){Poly r;r.a=(&x==&y)?pd::Conv<MOD>::sq(x.a):pd::Conv<MOD>::go(x.a,y.a);r.norm();zr r;}Poly sqr()zc{Poly r;r.a=pd::Conv<MOD>::sq(a);r.norm();zr r;}zf bool operator==(zc Poly&x,zc Poly&y){zr x.a==y.a;}zf bool operator!=(zc Poly&x,zc Poly&y){zr !(x==y);}Poly& operator+=(zc Poly&b){if(a.size()<b.size())a.resize(b.size());for(S i=0;i<b.size();i++)a[i]=O::add(a[i],b.a[i]);norm();zr *this;}Poly& operator-=(zc Poly&b){if(a.size()<b.size())a.resize(b.size());for(S i=0;i<b.size();i++)a[i]=O::sub(a[i],b.a[i]);norm();zr *this;}Poly& operator*=(zc Poly&b){zr *this=*this*b;}Poly operator-()zc{Poly r=*this;for(T&x:r.a)x=O::neg(x);zr r;}Poly& operator+=(T k){if(a.empty())a.resize(1);a[0]=O::add(a[0],k);norm();zr *this;}Poly& operator-=(T k){if(a.empty())a.resize(1);a[0]=O::sub(a[0],k);norm();zr *this;}Poly& operator*=(T k){for(T&x:a)x=O::mul(x,k);norm();zr *this;}Poly& operator/=(T k){zr *this*=O::inv(k);}zf Poly operator+(Poly x,T k){zr x+=k;}zf Poly operator+(T k,Poly x){zr x+=k;}zf Poly operator-(Poly x,T k){zr x-=k;}zf Poly operator-(T k,zc Poly&x){zr(-x)+k;}zf Poly operator*(Poly x,T k){zr x*=k;}zf Poly operator*(T k,Poly x){zr x*=k;}zf Poly operator/(Poly x,T k){zr x/=k;}Poly shl(S k)zc{if(empty())zr{};Poly r;r.a.assign(k,0);r.a.insert(r.a.end(),a.begin(),a.end());zr r;}Poly shr(S k)zc{if(k>=a.size())zr{};zr Poly(V<T>(a.begin()+k,a.end()));}zf Poly operator<<(zc Poly&x,S k){zr x.shl(k);}zf Poly operator>>(zc Poly&x,S k){zr x.shr(k);}Poly deriv()zc{if(a.size()<2)zr{};Poly r(a.size()-1);for(S i=1;i<a.size();i++)r.a[i-1]=O::mul(a[i],O::norm((u64)i));r.norm();zr r;}Poly integr()zc{Poly r(a.size()+1);for(S i=0;i<a.size();i++)r.a[i+1]=O::mul(a[i],inv_int(i+1));r.norm();zr r;}T eval(T x)zc{T r=0;for(S i=a.size();i--;)r=O::add(O::mul(r,x),a[i]);zr r;}T operator()(T x)zc{zr eval(x);}Poly inv(S n=0)zc{if(!n)n=a.size();assert(n&&!a.empty());zr inv_dispatch(n,std::integral_constant<bool,pd::DN<MOD>::yes>());}Poly inv_dispatch(S n,std::false_type)zc{Poly g{O::inv(a[0])};S m=1;while(m<n){S z=std::min(n,m<<1);Poly f=pre(z),t=(f*g).pre(z);t.a.resize(z);for(S i=0;i<z;i++)t.a[i]=O::neg(t.a[i]);t.a[0]=O::add(t.a[0],O::norm(2));g=(g*t).pre(z);m=z;}g.a.resize(n);g.norm();zr g;}Poly inv_dispatch(S n,std::true_type)zc{zd zy pd::DN<MOD>::N NN;Poly g{O::inv(a[0])};S m=1;while(m<n){S L=m<<1,z=std::min(n,L);if(NN::invext(a,g.a,z)){m=L;continue;}V<u32>f(L),gh(L),e(L);for(S i=0;i<std::min(a.size(),L);i++)f[i]=(u32)a[i];for(S i=0;i<m;i++)gh[i]=(u32)g.a[i];NN::ntt(f,0);NN::ntt(gh,0);for(S i=0;i<L;i++)f[i]=NN::mul(f[i],gh[i]);NN::ntt(f,1);for(S i=0;i<m;i++)e[i]=f[m+i];NN::ntt(e,0);for(S i=0;i<L;i++)e[i]=NN::mul(e[i],gh[i]);NN::ntt(e,1);g.a.resize(z);for(S i=m;i<z;i++)g.a[i]=O::neg((T)e[i-m]);m=L;}g.a.resize(n);g.norm();zr g;}Poly div(zc Poly&b,S n=0)zc{if(!n)n=a.size();zr(*this*b.inv(n)).pre(n);}Poly log(S n=0)zc{if(!n)n=a.size();assert(!a.empty()&&a[0]==O::norm(1));Poly r=(deriv()*inv(n)).pre(n-1).integr();r.a.resize(n);r.norm();zr r;}Poly exp(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);zr exp_dispatch(n,std::integral_constant<bool,pd::DN<MOD>::yes>());}Poly exp_dispatch(S n,std::false_type)zc{Poly g{1};S m=1;while(m<n){S z=std::min(n,m<<1);Poly q=pre(z)-g.log(z);q.a.resize(z);q.a[0]=O::add(q.a[0],O::norm(1));g=(g*q).pre(z);m=z;}g.a.resize(n);g.norm();zr g;}
Poly exp_dispatch(S n,std::true_type)zc{zd zy pd::DN<MOD>::N NN;Poly g{1};S m=1;while(m<n){S L=m<<1,z=std::min(n,L);Poly h=g.inv(L);V<u32>d(L),iv(L);for(S i=1;i<g.size();i++)d[i-1]=NN::mul((u32)g.a[i],(u32)(i%MOD));for(S i=0;i<h.size();i++)iv[i]=(u32)h.a[i];NN::ntt(d,0);NN::ntt(iv,0);for(S i=0;i<L;i++)d[i]=NN::mul(d[i],iv[i]);NN::ntt(d,1);V<u32>G(L),E(L);for(S i=0;i<g.size();i++)G[i]=(u32)g.a[i];for(S j=0;j<m&&m+j<z;j++){S k=m+j;u32 lg=NN::mul(d[k-1],(u32)inv_int(k));E[j]=NN::sub((u32)(k<a.size()?a[k]:0),lg);}NN::ntt(G,0);NN::ntt(E,0);for(S i=0;i<L;i++)G[i]=NN::mul(G[i],E[i]);NN::ntt(G,1);g.a.resize(z);for(S j=0;j<m&&m+j<z;j++)g.a[m+j]=(T)G[j];m=L;}g.a.resize(n);g.norm();zr g;}
zs T mod_sqrt(T n){
if(MOD==2)zr n;assert(MOD&&(MOD&1));if(!n)zr 0;if(O::pw(n,(MOD-1)>>1)!=1)zr 0;
if((MOD&3)==3)zr O::pw(n,(MOD+1)>>2);u64 q=MOD-1,s=0;while(!(q&1))q>>=1,++s;T z=2;while(O::pw(z,(MOD-1)>>1)!=MOD-1)z=O::add(z,1);
T c=O::pw(z,q),x=O::pw(n,(q+1)>>1),t=O::pw(n,q);u64 m=s;while(t!=1){u64 i=1;T tt=O::mul(t,t);while(i<m&&tt!=1)tt=O::mul(tt,tt),++i;T b=O::pw(c,u64(1)<<(m-i-1));x=O::mul(x,b);c=O::mul(b,b);t=O::mul(t,c);m=i;}zr x;
}
Poly sqrt(S n=0)zc{
if(!n)n=a.size();assert(MOD!=0);if(empty())zr{};S p=0;while(p<a.size()&&!a[p])++p;if(p){assert(!(p&1));Poly r=shr(p).sqrt(n-p/2);zr r.shl(p/2).pre(n);}T s=mod_sqrt(a[0]);assert(s);Poly g{s};T inv2=O::inv(O::norm(2));S m=1;
while(m<n){S z=std::min(n,m<<1);g=(g+(pre(z)*g.inv(z)).pre(z))*inv2;g.cut(z);m=z;}g.a.resize(n);g.norm();zr g;
}
Poly pow_scalar(T k,S n=0)zc{if(!n)n=a.size();assert(!empty()&&a[0]==O::norm(1));zr(log(n)*k).exp(n);}
Poly pow(u64 k,S n=0)zc{
if(!n)n=a.size();if(!n)zr{};if(k==0)zr Poly{O::norm(1)};
S p=0;while(p<a.size()&&!a[p])++p;if(p==a.size()||p>(n-1)/k)zr{};S sh=p*k;if(sh>=n)zr{};
T c=a[p],ic=O::inv(c);Poly f=shr(p)*ic;S need=n-sh;Poly r=(f.log(need)*O::norm(k)).exp(need);r*=O::pw(c,k);r=r.shl(sh);r.a.resize(n);r.norm();zr r;
}
Q<Poly,Poly> divmod(zc Poly&b)zc{
assert(!b.empty());if(a.size()<b.size())zr{{},*this};S n=a.size()-b.size()+1;Poly q=(rev().pre(n)*b.rev().inv(n)).pre(n).rev(n);Poly r=*this-q*b;r.cut(b.size()-1);zr{q,r};
}
zf Poly operator/(zc Poly&x,zc Poly&y){zr x.divmod(y).first;}zf Poly operator%(zc Poly&x,zc Poly&y){zr x.divmod(y).second;}Poly& operator/=(zc Poly&b){zr *this=*this/b;}Poly& operator%=(zc Poly&b){zr *this=*this%b;}
Poly compose(zc Poly&g,S n=0)zc{
if(!n)n=a.size();if(!n||empty())zr{};assert(g.empty()||g[0]==0);S m=1;while(m*m<n)++m;V<Poly>pw(m);pw[0]=Poly{O::norm(1)};for(S i=1;i<m;i++)pw[i]=(pw[i-1]*g).pre(n);Poly gm=(pw[m-1]*g).pre(n),res;S blocks=(std::min(a.size(),n)+m-1)/m;
for(S bb=blocks;bb--;){if(!res.empty())res=(res*gm).pre(n);Poly cur;cur.a.resize(n);S base=bb*m;for(S i=0;i<m&&base+i<a.size()&&base+i<n;i++){T c=a[base+i];if(!c)continue;for(S j=0;j<pw[i].size()&&j<n;j++)cur.a[j]=O::add(cur.a[j],O::mul(c,pw[i].a[j]));}cur.norm();res+=cur;res.cut(n);}zr res;
}
Poly revert(S n=0)zc{
if(!n)n=a.size();assert(n&&a.size()>1&&a[0]==0);if(n==1)zr{};Poly g(2);g.a[1]=O::inv(a[1]);S m=2;while(m<n){S z=std::min(n,m<<1);Poly e=compose(g,z);if(e.a.size()<2)e.a.resize(2);e.a[1]=O::sub(e.a[1],O::norm(1));e.norm();Poly d=deriv().compose(g,z);g=(g-e.div(d,z)).pre(z);m=z;}g.a.resize(n);g.norm();zr g;
}
Q<Poly,Poly> sincos(S n=0)zc{
if(!n)n=a.size();assert(MOD&&(empty()||a[0]==0));T I=mod_sqrt(O::neg(O::norm(1)));assert(I);Poly e=(*this*I).exp(n),ie=e.inv(n);T h=O::inv(O::norm(2)),hi=O::inv(O::mul(O::norm(2),I));zr{(e-ie)*hi,(e+ie)*h};
}
Poly sin(S n=0)zc{zr sincos(n).first;}Poly cos(S n=0)zc{zr sincos(n).second;}
Poly tan(S n=0)zc{if(!n)n=a.size();auto sc=sincos(n);zr sc.first.div(sc.second,n);}
Poly asin(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);Poly q=-pre(n).sqr().pre(n);q+=O::norm(1);zr(deriv()*q.sqrt(n).inv(n)).pre(n-1).integr().pre(n);}
Poly atan(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);Poly q=pre(n).sqr().pre(n);q+=O::norm(1);zr(deriv()*q.inv(n)).pre(n-1).integr().pre(n);}
Poly acos(T c0,S n=0)zc{if(!n)n=a.size();Poly r=-asin(n);r+=c0;zr r;}
V<T> chirpz(T z,S m)zc{
V<T>out(m);S n=a.size();if(!m||!n)zr out;if(!z){out[0]=eval(O::norm(1));for(S k=1;k<m;k++)out[k]=a[0];zr out;}T iz=O::inv(z);Poly A(n),B(n+m-1);T cur=1,q=1;for(S i=0;i<n;i++){A.a[i]=O::mul(a[i],cur);cur=O::mul(cur,q);q=O::mul(q,z);}S off=n-1;B.a[off]=1;cur=1;q=1;for(S t=1;t<n;t++){cur=O::mul(cur,q);B.a[off-t]=cur;q=O::mul(q,iz);}cur=1;q=iz;for(S j=1;j<m;j++){cur=O::mul(cur,q);B.a[off+j]=cur;q=O::mul(q,iz);}Poly C=A*B;cur=1;q=z;for(S k=0;k<m;k++){out[k]=O::mul(C[off+k],cur);cur=O::mul(cur,q);q=O::mul(q,z);}zr out;
}
Poly shift(T c)zc{
S n=a.size();if(!n)zr{};V<T> fac(n),ifac(n);fac[0]=1;for(S i=1;i<n;i++)fac[i]=O::mul(fac[i-1],O::norm((u64)i));ifac[n-1]=O::inv(fac[n-1]);for(S i=n-1;i;i--)ifac[i-1]=O::mul(ifac[i],O::norm((u64)i));
Poly A(n),B(n);for(S i=0;i<n;i++)A.a[n-1-i]=O::mul(a[i],fac[i]);T pw=1;for(S i=0;i<n;i++){B.a[i]=O::mul(pw,ifac[i]);pw=O::mul(pw,c);}Poly C=A*B,R(n);for(S i=0;i<n;i++)R.a[i]=O::mul(C[n-1-i],ifac[i]);R.norm();zr R;
}
V<T> multipoint(zc V<T>&xs)zc{
S n=xs.size();if(!n)zr{};S z=1;while(z<n)z<<=1;V<Poly>tr(z<<1);for(S i=0;i<z;i++)tr[z+i]=i<n?Poly{O::neg(xs[i]),O::norm(1)}:Poly{O::norm(1)};for(S i=z;i-- >1;)tr[i]=tr[i<<1]*tr[i<<1|1];V<Poly>rem(z<<1);rem[1]=*this%tr[1];for(S i=1;i<z;i++){rem[i<<1]=rem[i]%tr[i<<1];rem[i<<1|1]=rem[i]%tr[i<<1|1];}V<T>r(n);for(S i=0;i<n;i++)r[i]=rem[z+i].empty()?0:rem[z+i].a[0];zr r;
}
zs Poly interpolate(zc V<T>&xs,zc V<T>&ys){
S n=xs.size();assert(n==ys.size());if(!n)zr{};S z=1;while(z<n)z<<=1;V<Poly>tr(z<<1);for(S i=0;i<z;i++)tr[z+i]=i<n?Poly{O::neg(xs[i]),O::norm(1)}:Poly{O::norm(1)};for(S i=z;i-- >1;)tr[i]=tr[i<<1]*tr[i<<1|1];V<T>d=tr[1].deriv().multipoint(xs);V<Poly>v(z<<1);for(S i=0;i<n;i++)v[z+i]=Poly{O::mul(ys[i],O::inv(d[i]))};for(S i=n;i<z;i++)v[z+i]={};for(S i=z;i-- >1;)v[i]=v[i<<1]*tr[i<<1|1]+v[i<<1|1]*tr[i<<1];zr v[1].pre(n);
}
};
zt<u64 MOD> V<zy Poly<MOD>::T> berlekamp_massey(zc V<zy Poly<MOD>::T>&s){
zd Poly<MOD> P;zd zy P::T T;zd zy P::O O;V<T>C(1,1),B(1,1);int L=0,m=1;T b=1;
for(S n=0;n<s.size();n++){T d=s[n];for(int i=1;i<=L;i++)d=O::add(d,O::mul(C[i],s[n-i]));if(!d){++m;continue;}T coef=O::mul(d,O::inv(b));V<T>Tc=C;if(C.size()<B.size()+m)C.resize(B.size()+m);for(S j=0;j<B.size();j++)C[j+m]=O::sub(C[j+m],O::mul(coef,B[j]));if(2*L<=(int)n){L=(int)n+1-L;B=Tc;b=d;m=1;}else ++m;}C.erase(C.begin());for(T&x:C)x=O::neg(x);zr C;
}
zt<u64 MOD> zy Poly<MOD>::T bostan_mori(Poly<MOD> p,Poly<MOD> q,u64 k){
zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;assert(!q.empty()&&q.a[0]);
while(k){P qm=q;for(S i=1;i<qm.size();i+=2)qm.a[i]=O::neg(qm.a[i]);P s=p*qm,t=q*qm;V<T>np,nq;np.reserve((s.size()+1)/2);nq.reserve((t.size()+1)/2);for(S i=k&1;i<s.size();i+=2)np.push_back(s.a[i]);for(S i=0;i<t.size();i+=2)nq.push_back(t.a[i]);p=P(np);q=P(nq);k>>=1;}zr O::mul(p.empty()?0:p.a[0],O::inv(q.a[0]));
}
zt<u64 MOD> Poly<MOD> poly_gcd(Poly<MOD>a,Poly<MOD>b){zd zy Poly<MOD>::O O;while(!b.empty()){a%=b;std::swap(a,b);}if(!a.empty())a/=a.a.back();zr a;}
zt<u64 MOD> std::tuple<Poly<MOD>,Poly<MOD>,Poly<MOD> > poly_exgcd(Poly<MOD>a,Poly<MOD>b){zd Poly<MOD>P;P x0{1},x1,y0,y1{1};while(!b.empty()){auto qr=a.divmod(b);P nx=x0-qr.first*x1,ny=y0-qr.first*y1;a=b;b=qr.second;x0=x1;x1=nx;y0=y1;y1=ny;}if(!a.empty()){auto c=P::O::inv(a.a.back());a*=c;x0*=c;y0*=c;}zr std::make_tuple(a,x0,y0);}
zt<u64 MOD> zy Poly<MOD>::T resultant(Poly<MOD>a,Poly<MOD>b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;if(a.empty()||b.empty())zr 0;T ans=1;if(a.deg()<b.deg()){if((a.deg()*b.deg())&1)ans=O::neg(ans);std::swap(a,b);}for(;;){if(b.deg()==0)zr O::mul(ans,O::pw(b.a[0],a.deg()));P r=a%b;if(r.empty())zr 0;if((a.deg()*b.deg())&1)ans=O::neg(ans);ans=O::mul(ans,O::pw(b.a.back(),(u64)(a.deg()-r.deg())));a=b;b=r;}}
zt<u64 MOD> zy Poly<MOD>::T linear_nth(zc V<zy Poly<MOD>::T>&init,zc V<zy Poly<MOD>::T>&rec,u64 k){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;if(k<init.size())zr init[(S)k];S d=rec.size();assert(init.size()>=d&&d);P q(d+1);q.a[0]=1;for(S i=0;i<d;i++)q.a[i+1]=O::neg(rec[i]);P p=(P(V<T>(init.begin(),init.begin()+d))*q).pre(d);zr bostan_mori(p,q,k);}
zt<u64 MOD> void fwt_or(V<zy Poly<MOD>::T>&a,bool inv=false){zd zy Poly<MOD>::O O;for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++)a[i+j+l]=inv?O::sub(a[i+j+l],a[i+j]):O::add(a[i+j+l],a[i+j]);}
zt<u64 MOD> void fwt_and(V<zy Poly<MOD>::T>&a,bool inv=false){zd zy Poly<MOD>::O O;for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++)a[i+j]=inv?O::sub(a[i+j],a[i+j+l]):O::add(a[i+j],a[i+j+l]);}
zt<u64 MOD> void fwt_xor(V<zy Poly<MOD>::T>&a,bool inv=false){zd Poly<MOD>P;zd zy P::O O;zy P::T h=inv?O::inv(O::norm(2)):O::norm(1);for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++){auto x=a[i+j],y=a[i+j+l];a[i+j]=O::mul(O::add(x,y),h);a[i+j+l]=O::mul(O::sub(x,y),h);}}
zt<u64 MOD,int TYPE> V<zy Poly<MOD>::T> bitwise_convolution(V<zy Poly<MOD>::T>a,V<zy Poly<MOD>::T>b){assert(a.size()==b.size()&&!a.empty()&&!(a.size()&(a.size()-1)));if(TYPE==0)fwt_or<MOD>(a),fwt_or<MOD>(b);else if(TYPE==1)fwt_and<MOD>(a),fwt_and<MOD>(b);else fwt_xor<MOD>(a),fwt_xor<MOD>(b);for(S i=0;i<a.size();i++)a[i]=Poly<MOD>::O::mul(a[i],b[i]);if(TYPE==0)fwt_or<MOD>(a,1);else if(TYPE==1)fwt_and<MOD>(a,1);else fwt_xor<MOD>(a,1);zr a;}
zt<u64 MOD> zy Poly<MOD>::T lagrange_consecutive(zc V<zy Poly<MOD>::T>&y,zy Poly<MOD>::T x){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S n=y.size();if(!n)zr 0;V<T>pre(n+1),suf(n+1),fac(n),ifac(n);pre[0]=suf[n]=fac[0]=1;for(S i=0;i<n;i++)pre[i+1]=O::mul(pre[i],O::sub(x,O::norm((u64)i)));for(S i=n;i--;)suf[i]=O::mul(suf[i+1],O::sub(x,O::norm((u64)i)));for(S i=1;i<n;i++)fac[i]=O::mul(fac[i-1],O::norm((u64)i));ifac[n-1]=O::inv(fac[n-1]);for(S i=n-1;i;i--)ifac[i-1]=O::mul(ifac[i],O::norm((u64)i));T ans=0;for(S i=0;i<n;i++){T v=O::mul(y[i],O::mul(pre[i],suf[i+1]));v=O::mul(v,O::mul(ifac[i],ifac[n-1-i]));if((n-1-i)&1)v=O::neg(v);ans=O::add(ans,v);}zr ans;}
zt<u64 MOD> V<zy Poly<MOD>::T> subset_convolution(zc V<zy Poly<MOD>::T>&a,zc V<zy Poly<MOD>::T>&b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S N=a.size();assert(N==b.size()&&N&&!(N&(N-1)));int k=__builtin_ctzll(N);V<T>A((k+1)*N),B((k+1)*N),C((k+1)*N);for(S s=0;s<N;s++){int r=__builtin_popcountll(s);A[(S)r*N+s]=a[s];B[(S)r*N+s]=b[s];}for(int r=0;r<=k;r++)for(int bit=0;bit<k;bit++)for(S s=0;s<N;s++)if(s&(S(1)<<bit)){A[(S)r*N+s]=O::add(A[(S)r*N+s],A[(S)r*N+(s^(S(1)<<bit))]);B[(S)r*N+s]=O::add(B[(S)r*N+s],B[(S)r*N+(s^(S(1)<<bit))]);}for(S s=0;s<N;s++)for(int r=0;r<=k;r++)for(int i=0;i<=r;i++)C[(S)r*N+s]=O::add(C[(S)r*N+s],O::mul(A[(S)i*N+s],B[(S)(r-i)*N+s]));for(int r=0;r<=k;r++)for(int bit=0;bit<k;bit++)for(S s=0;s<N;s++)if(s&(S(1)<<bit))C[(S)r*N+s]=O::sub(C[(S)r*N+s],C[(S)r*N+(s^(S(1)<<bit))]);V<T>res(N);for(S s=0;s<N;s++)res[s]=C[(S)__builtin_popcountll(s)*N+s];zr res;}
zt<u64 MOD> V<zy Poly<MOD>::T> dirichlet_convolution(zc V<zy Poly<MOD>::T>&a,zc V<zy Poly<MOD>::T>&b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S n=std::min(a.size(),b.size());V<T>c(n);for(S i=1;i<n;i++)for(S j=1;i*j<n;j++)c[i*j]=O::add(c[i*j],O::mul(a[i],b[j]));zr c;}
inline V<u32> convolution_mod(zc V<u32>&a,zc V<u32>&b,u32 M){
if(a.empty()||b.empty())zr{};if(M==1)zr V<u32>(a.size()+b.size()-1);if(M==998244353u)zr pd::N1::conv(a,b);if(M==754974721u)zr pd::N2::conv(a,b);if(M==469762049u)zr pd::N3::conv(a,b);if(M==167772161u)zr pd::N4::conv(a,b);if(M==1224736769u)zr pd::N5::conv(a,b);if(std::min(a.size(),b.size())<=24){V<u32>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=(c[i+j]+(u64)(a[i]%M)*(b[j]%M))%M;zr c;}auto x=pd::N1::conv(a,b),y=pd::N2::conv(a,b),z=pd::N3::conv(a,b);V<u32>c(x.size());zs zc u64 i12=pd::I64(pd::P1%pd::P2,pd::P2),i123=pd::I64((u128)pd::P1*pd::P2%pd::P3,pd::P3);u64 q1=pd::P1%M,q12=q1*(pd::P2%M)%M;for(S i=0;i<c.size();i++){u64 t2=(u64)((y[i]+pd::P2-x[i]%pd::P2)%pd::P2)*i12%pd::P2,X=(u64)x[i]+pd::P1*t2,t3=(u64)((z[i]+pd::P3-X%pd::P3)%pd::P3)*i123%pd::P3,r=x[i]%M;r=(r+q1*(t2%M))%M;r=(r+q12*(t3%M))%M;c[i]=(u32)r;}zr c;
}
#undef zr
#undef zs
#undef zc
#undef zt
#undef zy
#undef zd
#undef zf
#endif
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define fst first
#define sed second
#define pref static inline
using namespace std;using hint=__int128;using uhint=unsigned __int128;
using us=unsigned short;using ui=unsigned int;using ll=long long;using ull=unsigned long long;
using db=double;using ldb=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;
using pil=pair<int,ll>;using pli=pair<ll,int>;using vi=vector<int>;using vl=vector<ll>;
using vpi=vector<pii>;using vpl=vector<pll>;using vpil=vector<pil>;using vpli=vector<pli>;
ostream& out128(ostream&,uhint,bool);ostream& operator<<(ostream&,hint);ostream& operator<<(ostream&,uhint);
namespace mystl{
const int SI=1<<22,SO=1<<20;pref size_t fr(void*p,size_t n){
#ifdef __linux__
return fread_unlocked(p,1,n,stdin);
#else
return fread(p,1,n,stdin);
#endif
}
unsigned char mp[1<<16];struct Init{Init(){memset(mp,255,sizeof mp);for(unsigned i=0;i<10;++i)for(unsigned j=0;j<10;++j){unsigned char s[2]={static_cast<unsigned char>('0'+i),static_cast<unsigned char>('0'+j)};uint16_t x;memcpy(&x,s,2);mp[x]=static_cast<unsigned char>(i*10+j);}}}init;
pref unsigned pv(const char*p){uint16_t x;memcpy(&x,p,2);return mp[x];}
struct IB:streambuf{
char b[SI];bool eofed=false;IB(){setg(b,b,b);}
int_type underflow()override{if(gptr()<egptr())return traits_type::to_int_type(*gptr());size_t n=fr(b,SI);if(!n)return traits_type::eof();setg(b,b,b+n);return traits_type::to_int_type(*gptr());}
inline void commit(char*p){gbump(static_cast<int>(p-gptr()));}
inline bool refill(char*&p,char*&e){commit(p);if(traits_type::eq_int_type(underflow(),traits_type::eof())){eofed=true;return false;}p=gptr();e=egptr();return true;}
inline bool head(char*&p,char*&e,bool&neg){eofed=false;for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}neg=false;if(*p=='-'||*p=='+'){neg=*p=='-';++p;if(p==e&&!refill(p,e))return false;}return true;}
template<class T,class U>inline bool slow(T&x,bool neg,char*&p,char*&e){U y=0;bool ok=false;for(;;){while(p<e){unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c>9){commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}ok=true;y=static_cast<U>(y*10+c);++p;}if(!refill(p,e)){if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}}}
template<class T,class U,int K>inline bool num(T&x){x=0;char*p=gptr(),*e=egptr();bool neg;if(!head(p,e,neg))return false;if(e-p<2*K+1)return slow<T,U>(x,neg,p,e);U y=0;bool ok=false;for(int i=0;i<K;++i){unsigned v=pv(p);if(v>=255)break;ok=true;y=static_cast<U>(y*100+static_cast<U>(v));p+=2;}unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c<=9){ok=true;y=static_cast<U>(y*10+c);++p;}commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}
inline bool read(short&x){return num<short,unsigned short,5>(x);}inline bool read(us&x){return num<us,us,5>(x);}inline bool read(int&x){return num<int,unsigned,5>(x);}inline bool read(unsigned&x){return num<unsigned,unsigned,5>(x);}inline bool read(long&x){return sizeof(long)<=4?num<long,unsigned long,5>(x):num<long,unsigned long,10>(x);}inline bool read(unsigned long&x){return sizeof(unsigned long)<=4?num<unsigned long,unsigned long,5>(x):num<unsigned long,unsigned long,10>(x);}inline bool read(ll&x){return num<ll,ull,10>(x);}inline bool read(ull&x){return num<ull,ull,10>(x);}inline bool read(hint&x){return num<hint,uhint,20>(x);}inline bool read(uhint&x){return num<uhint,uhint,20>(x);}
inline bool read(char&x){x=0;eofed=false;char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e){x=*p++;commit(p);return true;}if(!refill(p,e))return false;}}
inline bool read(string&x){eofed=false;x.clear();char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}for(;;){char*q=p;while(q<e&&static_cast<unsigned char>(*q)>32)++q;x.append(p,static_cast<size_t>(q-p));p=q;if(p<e){commit(p);return true;}if(!refill(p,e))return true;}}
template<class T>inline bool fp(T&x){x=0;string s;if(!read(s))return false;return cv(s.c_str(),x);}static inline bool cv(const char*s,float&x){char*e=nullptr;x=strtof(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,double&x){char*e=nullptr;x=strtod(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,long double&x){char*e=nullptr;x=strtold(s,&e);return e!=s&&*e==0;}
}ib;
struct OB:streambuf{
char b[SO];OB(){setp(b,b+SO);}~OB(){sync();}
int sync()override{size_t n=static_cast<size_t>(pptr()-pbase());if(n&&fwrite(b,1,n,stdout)!=n)return -1;setp(b,b+SO);return 0;}
int_type overflow(int_type c=traits_type::eof())override{if(sync())return traits_type::eof();if(!traits_type::eq_int_type(c,traits_type::eof()))*pptr()=traits_type::to_char_type(c),pbump(1);return traits_type::not_eof(c);}
inline void pc(char c){if(pptr()==epptr()&&traits_type::eq_int_type(overflow(),traits_type::eof()))return;*pptr()=c;pbump(1);}inline void ps(const char*s,size_t n){while(n){size_t k=static_cast<size_t>(epptr()-pptr());if(!k){if(traits_type::eq_int_type(overflow(),traits_type::eof()))return;k=static_cast<size_t>(epptr()-pptr());}k=min(k,n);memcpy(pptr(),s,k);pbump(static_cast<int>(k));s+=k;n-=k;}}
}ob;
struct FastIn:istream{
FastIn():istream(&ib){}using istream::operator>>;template<class T>inline FastIn&go(T&x){if(!ib.read(x))setstate(ib.eofed?ios::eofbit|ios::failbit:ios::failbit);else if(ib.eofed)setstate(ios::eofbit);return *this;}inline FastIn&operator>>(short&x){return go(x);}inline FastIn&operator>>(us&x){return go(x);}inline FastIn&operator>>(int&x){return go(x);}inline FastIn&operator>>(unsigned&x){return go(x);}inline FastIn&operator>>(long&x){return go(x);}inline FastIn&operator>>(unsigned long&x){return go(x);}inline FastIn&operator>>(ll&x){return go(x);}inline FastIn&operator>>(ull&x){return go(x);}inline FastIn&operator>>(hint&x){return go(x);}inline FastIn&operator>>(uhint&x){return go(x);}inline FastIn&operator>>(char&x){return go(x);}inline FastIn&operator>>(string&x){return go(x);}inline FastIn&operator>>(float&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(long double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(bool&x){int y=0;go(y);x=y!=0;return *this;}
}fin;
struct FastOut:ostream{
FastOut():ostream(&ob){}using ostream::operator<<;template<class U>inline FastOut&uo(U x){char s[64];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);while(n)ob.pc(s[--n]);return *this;}template<class T>inline FastOut&so(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}typedef typename make_unsigned<T>::type U;U y;if(x<0){ob.pc('-');y=U(0)-static_cast<U>(x);}else y=static_cast<U>(x);return uo(y);}template<class T>inline FastOut&un(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}
inline FastOut&operator<<(short x){return so(x);}inline FastOut&operator<<(us x){return un(x);}inline FastOut&operator<<(int x){return so(x);}inline FastOut&operator<<(unsigned x){return un(x);}inline FastOut&operator<<(long x){return so(x);}inline FastOut&operator<<(unsigned long x){return un(x);}inline FastOut&operator<<(ll x){return so(x);}inline FastOut&operator<<(ull x){return un(x);}inline FastOut&operator<<(bool x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}ob.pc(x?'1':'0');return *this;}inline FastOut&operator<<(char c){if(width()!=0){static_cast<ostream&>(*this)<<c;return *this;}ob.pc(c);return *this;}inline FastOut&operator<<(const char*s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s,strlen(s));return *this;}inline FastOut&operator<<(const string&s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s.data(),s.size());return *this;}inline FastOut&operator<<(float x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(double x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(long double x){static_cast<ostream&>(*this)<<x;return *this;}
inline FastOut&operator<<(hint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}uhint y;if(x<0){ob.pc('-');y=uhint(0)-static_cast<uhint>(x);}else y=static_cast<uhint>(x);return uo(y);}inline FastOut&operator<<(uhint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}FastOut&operator<<(ios_base&(*f)(ios_base&)){f(*this);return *this;}FastOut&operator<<(ostream&(*f)(ostream&)){f(*this);return *this;}FastOut&operator<<(ios&(*f)(ios&)){f(*this);return *this;}
}fout;
}
ostream& out128(ostream&out,uhint x,bool neg){char s[48];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);streamsize w=out.width(0),k=max<streamsize>(0,w-n-neg);char f=out.fill();ios::fmtflags a=out.flags()&ios::adjustfield;if(a==ios::left){if(neg)out.put('-');while(n)out.put(s[--n]);while(k--)out.put(f);}else if(a==ios::internal&&neg){out.put('-');while(k--)out.put(f);while(n)out.put(s[--n]);}else{while(k--)out.put(f);if(neg)out.put('-');while(n)out.put(s[--n]);}return out;}
ostream& operator<<(ostream&out,hint x){bool neg=x<0;return out128(out,neg?uhint(0)-static_cast<uhint>(x):static_cast<uhint>(x),neg);}ostream& operator<<(ostream&out,uhint x){return out128(out,x,false);}
#define cin mystl::fin
#define cout mystl::fout
namespace my{
const int N=1005;
template<typename T>pref T Min(T x,T y){return x<y?x:y;}
template<typename T>pref T Max(T x,T y){return x>y?x:y;}
using poly=vector<u32>;
int n,B;
poly f[N],g[N];
pref void trim(poly&a){
while(!a.empty()&&!a.back())a.pop_back();
}
pref poly mul(const poly&a,const poly&b){
return convolution_mod(a,b,n);
}
poly inv(const poly&a,int k){
poly b{1};
for(int len=1;len<k;len<<=1){
int m=Min(k,len<<1);
poly c(a.begin(),a.begin()+Min(m,(int)a.size()));
c=mul(c,b),c.resize(m);
for(auto&x:c)if(x)x=n-x;
c[0]=(c[0]+2ull)%n;
b=mul(b,c),b.resize(m);
}
return b;
}
poly rem(poly a,const poly&b){
trim(a);
if(a.size()<b.size())return a;
int k=a.size()-b.size()+1;
poly x=a,y=b;
reverse(x.begin(),x.end()),reverse(y.begin(),y.end());
x.resize(k);
poly q=mul(x,inv(y,k));
q.resize(k),reverse(q.begin(),q.end());
q=mul(q,b);
up(i,0,(int)a.size()-1)a[i]=((ll)a[i]-q[i]+n)%n;
a.resize(b.size()-1),trim(a);
return a;
}
void build(int p,int l,int r){
if(l==r){
f[p]={(u32)(l+1),1};
g[p]={(u32)((n-(ll)l*B%n)%n),1};
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
f[p]=mul(f[p<<1],f[p<<1|1]);
g[p]=mul(g[p<<1],g[p<<1|1]);
}
int dfs(int p,int l,int r,const poly&a){
if(l==r){
int d=__gcd(a.empty()?0:(int)a[0],n);
if(d==1)return 0;
if(d<n)return Max(d,n/d);
up(i,l*B+1,(l+1)*B){
d=__gcd(i,n);
if(d>1&&d<n)return Max(d,n/d);
}
return 0;
}
int mid=(l+r)>>1;
int ans=dfs(p<<1,l,mid,rem(a,g[p<<1]));
if(ans)return ans;
return dfs(p<<1|1,mid+1,r,rem(a,g[p<<1|1]));
}
pref void SOLVE(){
cin>>n;
B=1;
while((ll)B*B*B*B<n)B++;
build(1,0,B-1);
cout<<dfs(1,0,B-1,rem(f[1],g[1]))<<'\n';
}
}
int main(){
my::SOLVE();return 0;
}:::
对于 P4718
还是用
然后兴高采烈的写完！
考虑如何优化。
乘积树的多项式都是首一的，可以单独处理最高次项，缩短卷积。
和一些常数优化。
然而还是一样的结果。
注意到我的多项式板子在洛谷的模板题都在前两页，所以你们自己实现的时候应该还没我这个快。
考虑 miller-rabin 中有大量取模，考虑蒙哥马利约减继续卡常。
但是所得有限。
真的没办法了吗？
还有那位大人。。。
这就是我最后的波纹了。
然而还是没过。只能优化做法了。
考虑倍增。
就不用建树了。发现有了较大的提升。
这样复杂度就是
在经过进一步卡常后，快了一倍，但是仍只有 90pts！
显然我已经无法继续了。
:::error[90pts code]
//Author:kevinZ99
#ifndef KEVIN_POLY_ALL_HPP
#define KEVIN_POLY_ALL_HPP
#include <bits/stdc++.h>
#define zr return
#define zs static
#define zc const
#define zt template
#define zy typename
#define zd typedef
#define zf friend
zt<class T>using V=std::vector<T>;zt<class A,class B>using Q=std::pair<A,B>;using S=std::size_t;using u32=uint32_t;using u64=uint64_t;using u128=__uint128_t;using i128=__int128_t;
#ifndef PI
#define PI inline __attribute__((always_inline))
#endif
namespace pd{
zt<class T>struct SE:std::is_signed<T>{};zt<>struct SE<i128>:std::true_type{};zt<>struct SE<u128>:std::false_type{};PI u64 M64(u64 a,u64 b,u64 m){zr(u128)a*b%m;}PI u64 I64(u64 a,u64 m){
if(m==0){
assert(a&1);u64 x=a;for(int i=0;i<6;i++)x*=2-a*x;zr x;}i128 t=0,nt=1;u64 r=m,nr=a%m;while(nr){u64 q=r/nr,rr=r-q*nr;r=nr;nr=rr;i128 tt=t-(i128)q*nt;t=nt;nt=tt;}assert(r==1);if(t<0)t+=m;zr(u64)t;}zt<u64 MOD> struct CT{zd zy std::conditional<(MOD!=0 && MOD<=0xffffffffULL),u32,u64>::type type;};zt<u64 MOD> struct MO{
zd zy CT<MOD>::type T;zt<class U> zs PI T norm(U x){zr norm_impl(x,zy SE<U>::type());}zt<class U> zs PI T norm_impl(U x,std::true_type){
if(MOD==0)zr(T)(u64)x;i128 y=(i128)x%(i128)MOD;if(y<0)y+=MOD;zr(T)y;}zt<class U> zs PI T norm_impl(U x,std::false_type){zr MOD?(T)((u128)x%MOD):(T)(u64)x;}zs PI T add(T a,T b){
if(MOD==0)zr(T)(a+b);if(MOD<=0xffffffffULL){u64 s=(u64)a+b;if(s>=MOD)s-=MOD;zr(T)s;}u64 s=a+b;if(s<a || s>=MOD)s-=MOD;zr s;}zs PI T sub(T a,T b){if(MOD==0)zr(T)(a-b);zr a>=b?a-b:(T)(MOD-(u64)b+a);}zs PI T neg(T a){zr a?(MOD?T(MOD-a):T(0-a)):0;}zs PI T mul(T a,T b){if(MOD==0)zr(T)(a*b);if(MOD<=0xffffffffULL)zr(T)((u64)a*b%MOD);zr(T)((u128)a*b%MOD);}zs PI T inv(T a){zr(T)I64((u64)a,MOD);}zs PI T pw(T a,u64 e){T r=norm(1);for(;e;e>>=1,a=mul(a,a))if(e&1)r=mul(r,a);zr r;}};
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
#include <immintrin.h>
using X=__m256i;
#define PA __attribute__((target("avx2")))
#define PVL(x) _mm256_loadu_si256((const X*)(x))
#define PVS(x,v) _mm256_storeu_si256((X*)(x),v)
#define V0 _mm256_sub_epi32
#define V1 _mm256_add_epi32
#define V2 _mm256_setr_epi32
#define V3 _mm256_mul_epu32
#define V4 _mm256_blend_epi32
#define V5 _mm256_shuffle_epi32
#define V6 _mm256_set1_epi32
#define V7 _mm256_permutevar8x32_epi32
#define V8 _mm256_min_epu32
#define V9 _mm256_srli_epi64
#define VA _mm256_set1_epi64x
#define VB _mm256_permute4x64_epi64
#define VC _mm256_add_epi64
#define VD _mm256_set_epi64x
#define VE _mm256_permute2x128_si256
#define VF _mm256_or_si256
#define VG _mm256_srli_si256
#define VH _mm256_slli_epi64
zt<u32 P,u32 G>struct AN{
zs PI u32 sm(u32 a,u32 b){zr(u64)a*b%P;}zs u32 pw(u32 a,u32 e){u32 x=1;for(;e;e>>=1,a=sm(a,a))if(e&1)x=sm(x,a);zr x;}zs u32 ni32(){u32 x=1;for(int i=0;i<5;i++)x*=2-P*x;zr 0u-x;}
struct R{u32 ni,r,r2,w[4],wr[4];u64 wd[30][4],wid[30][4];u32 wl[30][8],wil[30][8];R(){ni=ni32();r=(u64(1)<<32)%P;r2=(u64)r*r%P;int l=__builtin_ctz(P-1);u32 x[31]={},y[31]={};x[l]=tm(pw(G,(P-1)>>l));y[l]=tm(pw(pw(G,(P-1)>>l),P-2));for(int i=l-1;i>=0;i--)x[i]=mm(x[i+1],x[i+1]),y[i]=mm(y[i+1],y[i+1]);w[0]=wr[0]=r;if(l>=2){w[1]=x[2];wr[1]=y[2];if(l>=3)w[2]=x[3],wr[2]=y[3],w[3]=mm(w[1],w[2]),wr[3]=mm(wr[1],wr[2]);}u32 a=r,b=r;for(int i=0;i<l-2;i++){u32 f=mm(a,x[i+3]),g=mm(b,y[i+3]);a=mm(a,y[i+3]);b=mm(b,x[i+3]);u32 f2=mm(f,f),g2=mm(g,g);u64 A[4]={f2,f,f2,f},B[4]={g2,g,g2,g};memcpy(wd[i],A,32);memcpy(wid[i],B,32);}a=b=r;for(int i=0;i<l-3;i++){u32 f=mm(a,x[i+4]),g=mm(b,y[i+4]);a=mm(a,y[i+4]);b=mm(b,x[i+4]);u32 f2=mm(f,f),f3=mm(f2,f2),g2=mm(g,g),g3=mm(g2,g2);u32 A[8]={f,f,f,f,f2,f2,f3,r},B[8]={g,g,g,g,g2,g2,g3,r};memcpy(wl[i],A,32);memcpy(wil[i],B,32);}}u32 rd(u64 x)zc{u32 m=(u32)x*ni,v=(u32)((x+(u64)m*P)>>32);zr v>=P?v-P:v;}u32 mm(u32 a,u32 b)zc{zr rd((u64)a*b);}u32 tm(u32 x)zc{zr mm(x,r2);}};
zs R&rr(){zs R x;zr x;}PA zs X ld(zc u32*x){zr PVL(x);}PA zs void st(u32*x,X v){PVS(x,v);}PA zs X sh(X x){X p=V6(P);zr V8(x,V0(x,p));}PA zs X ad(X a,X b){zr sh(V1(a,b));}PA zs X su(X a,X b){X d=V0(a,b);zr V8(d,V1(d,V6(P)));}
PA zs X mv(X a,X b,bool strict=true){R&q=rr();X ni=VA((u64)q.ni),p=VA(P),e=V3(a,b),o=V3(V9(a,32),V9(b,32));e=V9(VC(e,V3(V3(e,ni),p)),32);o=V9(VC(o,V3(V3(o,ni),p)),32);X z=VF(e,VH(o,32));zr strict?sh(z):z;}
PA zs X me(X a,X b,bool strict=true){R&q=rr();X ni=VA((u64)q.ni),p=VA(P),as=VG(a,4),e=V3(a,b),o=V3(as,b);e=VC(e,V3(V3(e,ni),p));o=VC(o,V3(V3(o,ni),p));X z=VF(VG(e,4),o);zr strict?sh(z):z;}
PA zs X h2(X x){X m=V6(P*2);zr V8(x,V0(x,m));}PA zs void hb(X a,X t,X&x,X&y){a=h2(a);x=V1(a,t);y=V0(V1(a,V6(P*2)),t);}PA zs void hi(X a,X b,X&x,X&y){a=h2(a);b=h2(b);x=V1(a,b);y=V0(V1(a,V6(P*2)),b);}zt<bool I,bool T>PA zs void b4(u32*a,u32*b,u32*c,u32*d,X w1,X w2,X w3){X A=sh(h2(ld(a))),B=sh(h2(ld(b))),C=sh(h2(ld(c))),D=sh(h2(ld(d)));if(!I){if(!T)C=mv(C,w1,false);{X x,y;hb(A,C,x,y);A=x;C=y;}if(!T)D=mv(D,w1,false);{X x,y;hb(B,D,x,y);B=x;D=y;}if(!T)B=me(B,w2,false);{X x,y;hb(A,B,x,y);A=x;B=y;}D=me(D,w3,false);{X x,y;hb(C,D,x,y);C=x;D=y;}}else{{X x,y;hi(A,B,x,y);if(!T)y=me(y,w2,false);A=x;B=y;}{X x,y;hi(C,D,x,y);y=me(y,w3,false);C=x;D=y;}{X x,y;hi(A,C,x,y);if(!T)y=mv(y,w1,false);A=x;C=y;}{X x,y;hi(B,D,x,y);if(!T)y=mv(y,w1,false);B=x;D=y;}}st(a,A);st(b,B);st(c,C);st(d,D);}
zt<bool I,bool T>PA zs void ax(int k,int o,u32*d,X&w){X w1=V5(w,0),w2=VB(w,0x55),w3=VB(w,0xff);int q=1<<k;for(int j=0;j<q;j+=8)b4<I,T>(d+o+j,d+o+q+j,d+o+2*q+j,d+o+3*q+j,w1,w2,w3);int z=__builtin_ctz(~(u32)o>>(k+2));w=mv(w,ld((u32*)(I?rr().wid[z]:rr().wd[z])));}
PA zs void lo(u32*d,X w0,X w1,X w2,X M){X v=ld(d);v=mv(v,w0,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w1,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w2,false);X x=V1(V4(v,V0(M,v),0xaa),V5(v,0xb1));st(d,V8(x,V0(x,M)));}
zt<bool T>PA zs void ax2(int k,int o,u32*a,u32*b,X&w){X w1=V5(w,0),w2=VB(w,0x55),w3=VB(w,0xff);int q=1<<k;for(int j=0;j<q;j+=8){b4<0,T>(a+o+j,a+o+q+j,a+o+2*q+j,a+o+3*q+j,w1,w2,w3);b4<0,T>(b+o+j,b+o+q+j,b+o+2*q+j,b+o+3*q+j,w1,w2,w3);}int z=__builtin_ctz(~(u32)o>>(k+2));w=mv(w,ld((u32*)rr().wd[z]));}
PA zs void fw2(int l,u32*a,u32*b){R&q=rr();if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(ld(a+j)),B=sh(ld(a+s+j)),C=sh(ld(b+j)),D=sh(ld(b+s+j));st(a+j,ad(A,B));st(a+s+j,su(A,B));st(b+j,ad(C,D));st(b+s+j,su(C,D));}}for(int k=l-2-(!(l&1));k>=3;k-=2){X w=VD(q.w[1],q.w[0],q.w[0],q.w[0]);ax2<1>(k,0,a,b,w);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax2<0>(k,i,a,b,w);}X w=V2(q.w[0],q.w[1],q.w[2],q.w[3],q.w[0],q.w[1],q.w[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C);lo(a+i,w0,w1,w2,M);lo(b+i,w0,w1,w2,M);if(i+8<(1<<l))w=mv(w,ld(q.wl[__builtin_ctz(~(u32)i>>3)]));}}
PA zs void fw(int l,u32*d){R&q=rr();if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(ld(d+j)),B=sh(ld(d+s+j));st(d+j,ad(A,B));st(d+s+j,su(A,B));}}for(int k=l-2-(!(l&1));k>=3;k-=2){X w=VD(q.w[1],q.w[0],q.w[0],q.w[0]);ax<0,1>(k,0,d,w);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax<0,0>(k,i,d,w);}X w=V2(q.w[0],q.w[1],q.w[2],q.w[3],q.w[0],q.w[1],q.w[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C),v=ld(d+i);v=mv(v,w0,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w1,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w2,false);v=V8(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),V0(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),M));st(d+i,v);if(i+8<(1<<l))w=mv(w,ld(q.wl[__builtin_ctz(~(u32)i>>3)]));}}
PA zs void iv(int l,u32*d,u32 ex=0){R&q=rr();X w=V2(q.wr[0],q.wr[1],q.wr[2],q.wr[3],q.wr[0],q.wr[1],q.wr[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C),v=ld(d+i);v=mv(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),w2,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w1,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w0,false);st(d+i,v);if(i+8<(1<<l))w=mv(w,ld(q.wil[__builtin_ctz(~(u32)i>>3)]));}for(int k=3;k+2<=l;k+=2){X z=VD(q.wr[1],q.wr[0],q.wr[0],q.wr[0]);ax<1,1>(k,0,d,z);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax<1,0>(k,i,d,z);}if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(h2(ld(d+j))),B=sh(h2(ld(d+s+j)));st(d+j,ad(A,B));st(d+s+j,su(A,B));}}u32 f=sm(pw(1u<<l,P-2),q.r);if(ex)f=sm(f,ex);X F=V6(f);for(int i=0;i<(1<<l);i+=8)st(d+i,mv(ld(d+i),F));}
zt<bool N,class A,class B>PA zs V<u32> conv(zc A&a,zc B&b){int z=1,n=(int)a.size()+(int)b.size()-1;while(z<n)z<<=1;V<u32>x(z),y(z);for(S i=0;i<a.size();i++)x[i]=N?(u32)a[i]:(u32)((u64)a[i]%P);for(S i=0;i<b.size();i++)y[i]=N?(u32)b[i]:(u32)((u64)b[i]%P);int l=__builtin_ctz((u32)z);fw2(l,x.data(),y.data());for(int i=0;i<z;i+=8)st(x.data()+i,mv(ld(x.data()+i),ld(y.data()+i),false));iv(l,x.data(),rr().r);x.resize(n);for(u32&v:x)if(v>=P)v-=P;zr x;}
zt<bool N,class A>PA zs V<u32> square(zc A&a){int z=1,n=(int)a.size()*2-1;while(z<n)z<<=1;V<u32>x(z);for(S i=0;i<a.size();i++)x[i]=N?(u32)a[i]:(u32)((u64)a[i]%P);int l=__builtin_ctz((u32)z);fw(l,x.data());for(int i=0;i<z;i+=8){X X=ld(x.data()+i);st(x.data()+i,mv(X,X,false));}iv(l,x.data(),rr().r);x.resize(n);for(u32&v:x)if(v>=P)v-=P;zr x;}
PA zs void normal_ntt(V<u32>&a,bool I){int l=__builtin_ctz((u32)a.size());if(I)iv(l,a.data());else fw(l,a.data());for(u32&v:a)if(v>=P)v-=P;}
PA zs void invext(zc V<u32>&f,V<u32>&g,S z){S m=g.size(),L=m<<1;V<u32>F(L),Q(L),E(L);for(S i=0;i<std::min(f.size(),L);i++)F[i]=f[i];for(S i=0;i<m;i++)Q[i]=g[i];int l=__builtin_ctz((u32)L);fw2(l,F.data(),Q.data());for(S i=0;i<L;i+=8)st(F.data()+i,mv(ld(F.data()+i),ld(Q.data()+i),false));iv(l,F.data(),rr().r);for(S i=0;i<m;i++)E[i]=F[m+i];fw(l,E.data());for(S i=0;i<L;i+=8)st(E.data()+i,mv(ld(E.data()+i),ld(Q.data()+i),false));iv(l,E.data(),rr().r);g.resize(z);for(S i=m;i<z;i++){u32 x=E[i-m];if(x>=P)x-=P;g[i]=x?P-x:0;}}
PA zs V<V<u32> > cross(zc V<u32>&al,zc V<u32>&ah,zc V<u32>&bl,zc V<u32>&bh,bool hh,int cap=0,int mode=0){int n=(int)al.size()+(int)bl.size()-1,z=1;while(z<n)z<<=1;if(cap)n=z=cap;V<u32>A(z),H(z),B(z),K(z),t(z);for(S i=0;i<al.size();i++)A[i]=al[i]%P,H[i]=ah[i]%P;for(S i=0;i<bl.size();i++)B[i]=bl[i]%P,K[i]=bh[i]%P;int l=__builtin_ctz((u32)z);fw2(l,A.data(),H.data());zs V<u32>cb,ck;if(mode==2)B=cb,K=ck;else{fw2(l,B.data(),K.data());if(mode==1)cb=B,ck=K;}V<V<u32> >r(hh?3:2,V<u32>(n));for(int c=0;c<(hh?3:2);c++){for(int i=0;i<z;i+=8){X x=c==0?mv(ld(A.data()+i),ld(B.data()+i),false):c==1?ad(mv(ld(A.data()+i),ld(K.data()+i)),mv(ld(H.data()+i),ld(B.data()+i))):mv(ld(H.data()+i),ld(K.data()+i),false);st(t.data()+i,x);}iv(l,t.data(),rr().r);for(int i=0;i<n;i++)r[c][i]=t[i]>=P?t[i]-P:t[i];}zr r;}
};
#undef PVL
#undef PVS
#endif
zt<u32 P,u32 G> struct NTT{
zs PI u32 add(u32 a,u32 b){u32 s=a+b;zr s>=P?s-P:s;}zs PI u32 sub(u32 a,u32 b){zr a>=b?a-b:a+P-b;}zs PI u32 mul(u32 a,u32 b){zr(u64)a*b%P;}zs PI u32 normv(u64 a){zr(u32)(a%P);}zs u32 pw(u32 a,u32 e){u32 r=1;for(;e;e>>=1,a=mul(a,a))if(e&1)r=mul(r,a);zr r;}zs bool avx(){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
zs zc bool x=(P<(1u<<30))&&__builtin_cpu_supports("avx2");zr x;
#undef V0
#undef V1
#undef V2
#undef V3
#undef V4
#undef V5
#undef V6
#undef V7
#undef V8
#undef V9
#undef VA
#undef VB
#undef VC
#undef VD
#undef VE
#undef VF
#undef VG
#undef VH
#else
zr false;
#endif
}zs void ntt(V<u32>&a,bool iv){assert((P-1)%a.size()==0);if(a.size()<=1)zr;
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx()&&a.size()>=8){AN<P,G>::normal_ntt(a,iv);zr;}
#endif
int n=(int)a.size();for(int i=1,j=0;i<n;i++){int b=n>>1;for(;j&b;b>>=1)j^=b;j^=b;if(i<j)std::swap(a[i],a[j]);}for(int l=2;l<=n;l<<=1){u32 w=pw(G,(P-1)/l);if(iv)w=pw(w,P-2);for(int i=0;i<n;i+=l){u32 x=1;for(int j=0;j<(l>>1);j++,x=mul(x,w)){u32 u=a[i+j],v=mul(a[i+j+(l>>1)],x);a[i+j]=add(u,v);a[i+j+(l>>1)]=sub(u,v);}}}if(iv){u32 x=pw(n,P-2);for(u32&v:a)v=mul(v,x);}}zs bool invext(zc V<u32>&f,V<u32>&g,S z){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx()&&(g.size()<<1)>=8){AN<P,G>::invext(f,g,z);zr true;}
#endif
zr false;}zt<bool NORMAL,class A,class B> zs V<u32> cv(zc A&a,zc B&b){if(a.empty()||b.empty())zr{};if(std::min(a.size(),b.size())<=56){V<u32>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=(c[i+j]+(u64)(u32)a[i]*(u32)b[j])%P;zr c;}
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::zt conv<NORMAL>(a,b);
#endif
int z=1,need=(int)a.size()+(int)b.size()-1;while(z<need)z<<=1;V<u32>x(z),y(z);for(S i=0;i<a.size();i++)x[i]=NORMAL?(u32)a[i]:(u32)((u64)a[i]%P);for(S i=0;i<b.size();i++)y[i]=NORMAL?(u32)b[i]:(u32)((u64)b[i]%P);ntt(x,0);ntt(y,0);for(int i=0;i<z;i++)x[i]=mul(x[i],y[i]);ntt(x,1);x.resize(need);zr x;}zt<class A,class B> zs V<u32> conv(zc A&a,zc B&b){zr cv<false>(a,b);}zt<class A,class B> zs V<u32> conv_norm(zc A&a,zc B&b){zr cv<true>(a,b);}zt<class A> zs V<u32> square_norm(zc A&a){if(a.empty())zr{};if(a.size()<=56)zr cv<true>(a,a);
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::zt square<true>(a);
#endif
int z=1,need=(int)a.size()*2-1;while(z<need)z<<=1;V<u32>x(z);std::copy(a.begin(),a.end(),x.begin());ntt(x,0);for(int i=0;i<z;i++)x[i]=mul(x[i],x[i]);ntt(x,1);x.resize(need);zr x;}zs V<V<u32> > cross(zc V<u32>&al,zc V<u32>&ah,zc V<u32>&bl,zc V<u32>&bh,bool hh,int cap=0,int mode=0){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::cross(al,ah,bl,bh,hh,cap,mode);
#endif
int need=(int)al.size()+(int)bl.size()-1,z=1;while(z<need)z<<=1;if(cap)need=z=cap;V<u32>A(z),H(z),B(z),K(z),t(z);for(S i=0;i<al.size();i++)A[i]=al[i]%P,H[i]=ah[i]%P;for(S i=0;i<bl.size();i++)B[i]=bl[i]%P,K[i]=bh[i]%P;ntt(A,0);ntt(H,0);zs V<u32>cb,ck;if(mode==2)B=cb,K=ck;else{ntt(B,0);ntt(K,0);if(mode==1)cb=B,ck=K;}V<V<u32> >r(hh?3:2,V<u32>(need));for(int c=0;c<(hh?3:2);c++){for(int i=0;i<z;i++)t[i]=c==0?mul(A[i],B[i]):c==1?add(mul(A[i],K[i]),mul(H[i],B[i])):mul(H[i],K[i]);ntt(t,1);std::copy(t.begin(),t.begin()+need,r[c].begin());}zr r;}};using N1=NTT<998244353,3>;using N2=NTT<754974721,11>;using N3=NTT<469762049,3>;using N4=NTT<167772161,3>;using N5=NTT<1224736769,3>;zs zc u64 P1=998244353ULL,P2=754974721ULL,P3=469762049ULL;PI u128 crt3(u32 a,u32 b,u32 c){zs zc u64 i12=I64(P1%P2,P2),i123=I64((u128)P1*P2%P3,P3);u64 t2=(u64)((b+P2-a%P2)%P2)*i12%P2,x=(u64)a+P1*t2,t3=(u64)((c+P3-x%P3)%P3)*i123%P3;zr(u128)x+(u128)P1*P2*t3;}zt<u64 M> PI u32 crt3m(u32 a,u32 b,u32 c){zs zc u64 i12=I64(P1%P2,P2),i123=I64((u128)P1*P2%P3,P3),q1=P1%M,q12=q1*(P2%M)%M;u64 t2=(u64)((b+P2-a%P2)%P2)*i12%P2,x=(u64)a+P1*t2,t3=(u64)((c+P3-x%P3)%P3)*i123%P3,r=a%M;r=(r+q1*(t2%M)%M)%M;r=(r+q12*(t3%M)%M)%M;zr(u32)r;}zt<u64 MOD> struct DN{enum{yes=0};};zt<>struct DN<998244353ULL>{enum{yes=1};zd N1 N;};zt<>struct DN<754974721ULL>{enum{yes=1};zd N2 N;};zt<>struct DN<469762049ULL>{enum{yes=1};zd N3 N;};zt<>struct DN<167772161ULL>{enum{yes=1};zd N4 N;};zt<>struct DN<1224736769ULL>{enum{yes=1};zd N5 N;};zt<u64 MOD,bool DIRECT=DN<MOD>::yes> struct Conv;zt<u64 MOD>struct Conv<MOD,true>{zd zy CT<MOD>::type T;zs V<T>go(zc V<T>&a,zc V<T>&b){zd zy DN<MOD>::N N;zr N::conv_norm(a,b);}zs V<T>sq(zc V<T>&a){zd zy DN<MOD>::N N;zr N::square_norm(a);}};zt<u64 MOD>struct Conv<MOD,false>{zd zy CT<MOD>::type T;zs V<T>naive(zc V<T>&a,zc V<T>&b){V<T>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=MO<MOD>::add(c[i+j],MO<MOD>::mul(a[i],b[j]));zr c;}zs V<T>go32(zc V<T>&a,zc V<T>&b){auto x=N1::conv(a,b),y=N2::conv(a,b),z=N3::conv(a,b);V<T>c(x.size());for(S i=0;i<c.size();i++)c[i]=(T)crt3m<MOD>(x[i],y[i],z[i]);zr c;}zs V<T>go64(zc V<T>&a,zc V<T>&b){V<u32>al(a.size()),ah(a.size()),bl(b.size()),bh(b.size());for(S i=0;i<a.size();i++)al[i]=(u32)a[i],ah[i]=(u32)((u64)a[i]>>32);for(S i=0;i<b.size();i++)bl[i]=(u32)b[i],bh[i]=(u32)((u64)b[i]>>32);bool h=MOD!=0;auto r1=N1::cross(al,ah,bl,bh,h),r2=N2::cross(al,ah,bl,bh,h),r3=N3::cross(al,ah,bl,bh,h);V<T>c(r1[0].size());if(MOD==0){for(S i=0;i<c.size();i++){u64 lo=(u64)crt3(r1[0][i],r2[0][i],r3[0][i]),cr=(u64)crt3(r1[1][i],r2[1][i],r3[1][i]);c[i]=(T)(lo+(cr<<32));}}else{u64 r64=(u64)((u128(1)<<64)%MOD);for(S i=0;i<c.size();i++){u64 lo=(u64)(crt3(r1[0][i],r2[0][i],r3[0][i])%MOD),cr=(u64)(crt3(r1[1][i],r2[1][i],r3[1][i])%MOD),hi=(u64)(crt3(r1[2][i],r2[2][i],r3[2][i])%MOD),x=(u64)(((u128)lo+((u128)cr<<32))%MOD);c[i]=(T)MO<MOD>::add((T)x,(T)M64(hi,r64,MOD));}}zr c;}zs V<T>go(zc V<T>&a,zc V<T>&b){if(a.empty()||b.empty())zr{};if(std::min(a.size(),b.size())<=24)zr naive(a,b);zr go_dispatch(a,b,std::integral_constant<bool,(MOD!=0&&MOD<=0xffffffffULL)>());}zs V<T>sq(zc V<T>&a){zr go(a,a);}zs V<T>go_dispatch(zc V<T>&a,zc V<T>&b,std::true_type){zr go32(a,b);}zs V<T>go_dispatch(zc V<T>&a,zc V<T>&b,std::false_type){zr go64(a,b);}};}zt<u64 MOD> struct Poly{
zd zy pd::CT<MOD>::type T;zd pd::MO<MOD> O;V<T>a;Poly(){}Poly(S n):a(n){}Poly(zc V<T>&v):a(v){norm();}zt<class U> Poly(zc V<U>&v){a.resize(v.size());for(S i=0;i<v.size();i++)a[i]=O::norm(v[i]);norm();}zt<class U> Poly(std::initializer_list<U> v){a.reserve(v.size());for(auto x:v)a.push_back(O::norm(x));norm();}S size()zc{zr a.size();}bool empty()zc{zr a.empty();}int deg()zc{zr(int)a.size()-1;}T operator[](S i)zc{zr i<a.size()?a[i]:0;}T& operator[](S i){zr a[i];}zs T inv_int(S x){zr inv_int_dispatch(x,std::integral_constant<bool,pd::DN<MOD>::yes>());}zs T inv_int_dispatch(S x,std::false_type){zr O::inv(O::norm((u64)x));}zs T inv_int_dispatch(S x,std::true_type){assert(x&&x<MOD);zs V<T>v(2,1);v[0]=0;if(v.size()<=x){S o=v.size();v.resize(x+1);for(S i=o;i<=x;i++)v[i]=(T)(MOD-(u64)(MOD/i)*v[MOD%i]%MOD);}zr v[x];}void norm(){while(!a.empty()&&a.back()==0)a.pop_back();}Poly pre(S n)zc{if(a.size()<=n)zr *this;Poly r=*this;r.a.resize(n);r.norm();zr r;}Poly& cut(S n){if(a.size()>n)a.resize(n);norm();zr *this;}Poly rev(S n=0)zc{Poly r=*this;if(n)r.a.resize(n);std::reverse(r.a.begin(),r.a.end());r.norm();zr r;}zf Poly operator+(Poly x,zc Poly&y){zr x+=y;}zf Poly operator-(Poly x,zc Poly&y){zr x-=y;}zf Poly operator*(zc Poly&x,zc Poly&y){Poly r;r.a=(&x==&y)?pd::Conv<MOD>::sq(x.a):pd::Conv<MOD>::go(x.a,y.a);r.norm();zr r;}Poly sqr()zc{Poly r;r.a=pd::Conv<MOD>::sq(a);r.norm();zr r;}zf bool operator==(zc Poly&x,zc Poly&y){zr x.a==y.a;}zf bool operator!=(zc Poly&x,zc Poly&y){zr !(x==y);}Poly& operator+=(zc Poly&b){if(a.size()<b.size())a.resize(b.size());for(S i=0;i<b.size();i++)a[i]=O::add(a[i],b.a[i]);norm();zr *this;}Poly& operator-=(zc Poly&b){if(a.size()<b.size())a.resize(b.size());for(S i=0;i<b.size();i++)a[i]=O::sub(a[i],b.a[i]);norm();zr *this;}Poly& operator*=(zc Poly&b){zr *this=*this*b;}Poly operator-()zc{Poly r=*this;for(T&x:r.a)x=O::neg(x);zr r;}Poly& operator+=(T k){if(a.empty())a.resize(1);a[0]=O::add(a[0],k);norm();zr *this;}Poly& operator-=(T k){if(a.empty())a.resize(1);a[0]=O::sub(a[0],k);norm();zr *this;}Poly& operator*=(T k){for(T&x:a)x=O::mul(x,k);norm();zr *this;}Poly& operator/=(T k){zr *this*=O::inv(k);}zf Poly operator+(Poly x,T k){zr x+=k;}zf Poly operator+(T k,Poly x){zr x+=k;}zf Poly operator-(Poly x,T k){zr x-=k;}zf Poly operator-(T k,zc Poly&x){zr(-x)+k;}zf Poly operator*(Poly x,T k){zr x*=k;}zf Poly operator*(T k,Poly x){zr x*=k;}zf Poly operator/(Poly x,T k){zr x/=k;}Poly shl(S k)zc{if(empty())zr{};Poly r;r.a.assign(k,0);r.a.insert(r.a.end(),a.begin(),a.end());zr r;}Poly shr(S k)zc{if(k>=a.size())zr{};zr Poly(V<T>(a.begin()+k,a.end()));}zf Poly operator<<(zc Poly&x,S k){zr x.shl(k);}zf Poly operator>>(zc Poly&x,S k){zr x.shr(k);}Poly deriv()zc{if(a.size()<2)zr{};Poly r(a.size()-1);for(S i=1;i<a.size();i++)r.a[i-1]=O::mul(a[i],O::norm((u64)i));r.norm();zr r;}Poly integr()zc{Poly r(a.size()+1);for(S i=0;i<a.size();i++)r.a[i+1]=O::mul(a[i],inv_int(i+1));r.norm();zr r;}T eval(T x)zc{T r=0;for(S i=a.size();i--;)r=O::add(O::mul(r,x),a[i]);zr r;}T operator()(T x)zc{zr eval(x);}Poly inv(S n=0)zc{if(!n)n=a.size();assert(n&&!a.empty());zr inv_dispatch(n,std::integral_constant<bool,pd::DN<MOD>::yes>());}Poly inv_dispatch(S n,std::false_type)zc{Poly g{O::inv(a[0])};S m=1;while(m<n){S z=std::min(n,m<<1);Poly f=pre(z),t=(f*g).pre(z);t.a.resize(z);for(S i=0;i<z;i++)t.a[i]=O::neg(t.a[i]);t.a[0]=O::add(t.a[0],O::norm(2));g=(g*t).pre(z);m=z;}g.a.resize(n);g.norm();zr g;}Poly inv_dispatch(S n,std::true_type)zc{zd zy pd::DN<MOD>::N NN;Poly g{O::inv(a[0])};S m=1;while(m<n){S L=m<<1,z=std::min(n,L);if(NN::invext(a,g.a,z)){m=L;continue;}V<u32>f(L),gh(L),e(L);for(S i=0;i<std::min(a.size(),L);i++)f[i]=(u32)a[i];for(S i=0;i<m;i++)gh[i]=(u32)g.a[i];NN::ntt(f,0);NN::ntt(gh,0);for(S i=0;i<L;i++)f[i]=NN::mul(f[i],gh[i]);NN::ntt(f,1);for(S i=0;i<m;i++)e[i]=f[m+i];NN::ntt(e,0);for(S i=0;i<L;i++)e[i]=NN::mul(e[i],gh[i]);NN::ntt(e,1);g.a.resize(z);for(S i=m;i<z;i++)g.a[i]=O::neg((T)e[i-m]);m=L;}g.a.resize(n);g.norm();zr g;}Poly div(zc Poly&b,S n=0)zc{if(!n)n=a.size();zr(*this*b.inv(n)).pre(n);}Poly log(S n=0)zc{if(!n)n=a.size();assert(!a.empty()&&a[0]==O::norm(1));Poly r=(deriv()*inv(n)).pre(n-1).integr();r.a.resize(n);r.norm();zr r;}Poly exp(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);zr exp_dispatch(n,std::integral_constant<bool,pd::DN<MOD>::yes>());}Poly exp_dispatch(S n,std::false_type)zc{Poly g{1};S m=1;while(m<n){S z=std::min(n,m<<1);Poly q=pre(z)-g.log(z);q.a.resize(z);q.a[0]=O::add(q.a[0],O::norm(1));g=(g*q).pre(z);m=z;}g.a.resize(n);g.norm();zr g;}
Poly exp_dispatch(S n,std::true_type)zc{zd zy pd::DN<MOD>::N NN;Poly g{1};S m=1;while(m<n){S L=m<<1,z=std::min(n,L);Poly h=g.inv(L);V<u32>d(L),iv(L);for(S i=1;i<g.size();i++)d[i-1]=NN::mul((u32)g.a[i],(u32)(i%MOD));for(S i=0;i<h.size();i++)iv[i]=(u32)h.a[i];NN::ntt(d,0);NN::ntt(iv,0);for(S i=0;i<L;i++)d[i]=NN::mul(d[i],iv[i]);NN::ntt(d,1);V<u32>G(L),E(L);for(S i=0;i<g.size();i++)G[i]=(u32)g.a[i];for(S j=0;j<m&&m+j<z;j++){S k=m+j;u32 lg=NN::mul(d[k-1],(u32)inv_int(k));E[j]=NN::sub((u32)(k<a.size()?a[k]:0),lg);}NN::ntt(G,0);NN::ntt(E,0);for(S i=0;i<L;i++)G[i]=NN::mul(G[i],E[i]);NN::ntt(G,1);g.a.resize(z);for(S j=0;j<m&&m+j<z;j++)g.a[m+j]=(T)G[j];m=L;}g.a.resize(n);g.norm();zr g;}
zs T mod_sqrt(T n){
if(MOD==2)zr n;assert(MOD&&(MOD&1));if(!n)zr 0;if(O::pw(n,(MOD-1)>>1)!=1)zr 0;
if((MOD&3)==3)zr O::pw(n,(MOD+1)>>2);u64 q=MOD-1,s=0;while(!(q&1))q>>=1,++s;T z=2;while(O::pw(z,(MOD-1)>>1)!=MOD-1)z=O::add(z,1);
T c=O::pw(z,q),x=O::pw(n,(q+1)>>1),t=O::pw(n,q);u64 m=s;while(t!=1){u64 i=1;T tt=O::mul(t,t);while(i<m&&tt!=1)tt=O::mul(tt,tt),++i;T b=O::pw(c,u64(1)<<(m-i-1));x=O::mul(x,b);c=O::mul(b,b);t=O::mul(t,c);m=i;}zr x;
}
Poly sqrt(S n=0)zc{
if(!n)n=a.size();assert(MOD!=0);if(empty())zr{};S p=0;while(p<a.size()&&!a[p])++p;if(p){assert(!(p&1));Poly r=shr(p).sqrt(n-p/2);zr r.shl(p/2).pre(n);}T s=mod_sqrt(a[0]);assert(s);Poly g{s};T inv2=O::inv(O::norm(2));S m=1;
while(m<n){S z=std::min(n,m<<1);g=(g+(pre(z)*g.inv(z)).pre(z))*inv2;g.cut(z);m=z;}g.a.resize(n);g.norm();zr g;
}
Poly pow_scalar(T k,S n=0)zc{if(!n)n=a.size();assert(!empty()&&a[0]==O::norm(1));zr(log(n)*k).exp(n);}
Poly pow(u64 k,S n=0)zc{
if(!n)n=a.size();if(!n)zr{};if(k==0)zr Poly{O::norm(1)};
S p=0;while(p<a.size()&&!a[p])++p;if(p==a.size()||p>(n-1)/k)zr{};S sh=p*k;if(sh>=n)zr{};
T c=a[p],ic=O::inv(c);Poly f=shr(p)*ic;S need=n-sh;Poly r=(f.log(need)*O::norm(k)).exp(need);r*=O::pw(c,k);r=r.shl(sh);r.a.resize(n);r.norm();zr r;
}
Q<Poly,Poly> divmod(zc Poly&b)zc{
assert(!b.empty());if(a.size()<b.size())zr{{},*this};S n=a.size()-b.size()+1;Poly q=(rev().pre(n)*b.rev().inv(n)).pre(n).rev(n);Poly r=*this-q*b;r.cut(b.size()-1);zr{q,r};
}
zf Poly operator/(zc Poly&x,zc Poly&y){zr x.divmod(y).first;}zf Poly operator%(zc Poly&x,zc Poly&y){zr x.divmod(y).second;}Poly& operator/=(zc Poly&b){zr *this=*this/b;}Poly& operator%=(zc Poly&b){zr *this=*this%b;}
Poly compose(zc Poly&g,S n=0)zc{
if(!n)n=a.size();if(!n||empty())zr{};assert(g.empty()||g[0]==0);S m=1;while(m*m<n)++m;V<Poly>pw(m);pw[0]=Poly{O::norm(1)};for(S i=1;i<m;i++)pw[i]=(pw[i-1]*g).pre(n);Poly gm=(pw[m-1]*g).pre(n),res;S blocks=(std::min(a.size(),n)+m-1)/m;
for(S bb=blocks;bb--;){if(!res.empty())res=(res*gm).pre(n);Poly cur;cur.a.resize(n);S base=bb*m;for(S i=0;i<m&&base+i<a.size()&&base+i<n;i++){T c=a[base+i];if(!c)continue;for(S j=0;j<pw[i].size()&&j<n;j++)cur.a[j]=O::add(cur.a[j],O::mul(c,pw[i].a[j]));}cur.norm();res+=cur;res.cut(n);}zr res;
}
Poly revert(S n=0)zc{
if(!n)n=a.size();assert(n&&a.size()>1&&a[0]==0);if(n==1)zr{};Poly g(2);g.a[1]=O::inv(a[1]);S m=2;while(m<n){S z=std::min(n,m<<1);Poly e=compose(g,z);if(e.a.size()<2)e.a.resize(2);e.a[1]=O::sub(e.a[1],O::norm(1));e.norm();Poly d=deriv().compose(g,z);g=(g-e.div(d,z)).pre(z);m=z;}g.a.resize(n);g.norm();zr g;
}
Q<Poly,Poly> sincos(S n=0)zc{
if(!n)n=a.size();assert(MOD&&(empty()||a[0]==0));T I=mod_sqrt(O::neg(O::norm(1)));assert(I);Poly e=(*this*I).exp(n),ie=e.inv(n);T h=O::inv(O::norm(2)),hi=O::inv(O::mul(O::norm(2),I));zr{(e-ie)*hi,(e+ie)*h};
}
Poly sin(S n=0)zc{zr sincos(n).first;}Poly cos(S n=0)zc{zr sincos(n).second;}
Poly tan(S n=0)zc{if(!n)n=a.size();auto sc=sincos(n);zr sc.first.div(sc.second,n);}
Poly asin(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);Poly q=-pre(n).sqr().pre(n);q+=O::norm(1);zr(deriv()*q.sqrt(n).inv(n)).pre(n-1).integr().pre(n);}
Poly atan(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);Poly q=pre(n).sqr().pre(n);q+=O::norm(1);zr(deriv()*q.inv(n)).pre(n-1).integr().pre(n);}
Poly acos(T c0,S n=0)zc{if(!n)n=a.size();Poly r=-asin(n);r+=c0;zr r;}
V<T> chirpz(T z,S m)zc{
V<T>out(m);S n=a.size();if(!m||!n)zr out;if(!z){out[0]=eval(O::norm(1));for(S k=1;k<m;k++)out[k]=a[0];zr out;}T iz=O::inv(z);Poly A(n),B(n+m-1);T cur=1,q=1;for(S i=0;i<n;i++){A.a[i]=O::mul(a[i],cur);cur=O::mul(cur,q);q=O::mul(q,z);}S off=n-1;B.a[off]=1;cur=1;q=1;for(S t=1;t<n;t++){cur=O::mul(cur,q);B.a[off-t]=cur;q=O::mul(q,iz);}cur=1;q=iz;for(S j=1;j<m;j++){cur=O::mul(cur,q);B.a[off+j]=cur;q=O::mul(q,iz);}Poly C=A*B;cur=1;q=z;for(S k=0;k<m;k++){out[k]=O::mul(C[off+k],cur);cur=O::mul(cur,q);q=O::mul(q,z);}zr out;
}
Poly shift(T c)zc{
S n=a.size();if(!n)zr{};V<T> fac(n),ifac(n);fac[0]=1;for(S i=1;i<n;i++)fac[i]=O::mul(fac[i-1],O::norm((u64)i));ifac[n-1]=O::inv(fac[n-1]);for(S i=n-1;i;i--)ifac[i-1]=O::mul(ifac[i],O::norm((u64)i));
Poly A(n),B(n);for(S i=0;i<n;i++)A.a[n-1-i]=O::mul(a[i],fac[i]);T pw=1;for(S i=0;i<n;i++){B.a[i]=O::mul(pw,ifac[i]);pw=O::mul(pw,c);}Poly C=A*B,R(n);for(S i=0;i<n;i++)R.a[i]=O::mul(C[n-1-i],ifac[i]);R.norm();zr R;
}
V<T> multipoint(zc V<T>&xs)zc{
S n=xs.size();if(!n)zr{};S z=1;while(z<n)z<<=1;V<Poly>tr(z<<1);for(S i=0;i<z;i++)tr[z+i]=i<n?Poly{O::neg(xs[i]),O::norm(1)}:Poly{O::norm(1)};for(S i=z;i-- >1;)tr[i]=tr[i<<1]*tr[i<<1|1];V<Poly>rem(z<<1);rem[1]=*this%tr[1];for(S i=1;i<z;i++){rem[i<<1]=rem[i]%tr[i<<1];rem[i<<1|1]=rem[i]%tr[i<<1|1];}V<T>r(n);for(S i=0;i<n;i++)r[i]=rem[z+i].empty()?0:rem[z+i].a[0];zr r;
}
zs Poly interpolate(zc V<T>&xs,zc V<T>&ys){
S n=xs.size();assert(n==ys.size());if(!n)zr{};S z=1;while(z<n)z<<=1;V<Poly>tr(z<<1);for(S i=0;i<z;i++)tr[z+i]=i<n?Poly{O::neg(xs[i]),O::norm(1)}:Poly{O::norm(1)};for(S i=z;i-- >1;)tr[i]=tr[i<<1]*tr[i<<1|1];V<T>d=tr[1].deriv().multipoint(xs);V<Poly>v(z<<1);for(S i=0;i<n;i++)v[z+i]=Poly{O::mul(ys[i],O::inv(d[i]))};for(S i=n;i<z;i++)v[z+i]={};for(S i=z;i-- >1;)v[i]=v[i<<1]*tr[i<<1|1]+v[i<<1|1]*tr[i<<1];zr v[1].pre(n);
}
};
zt<u64 MOD> V<zy Poly<MOD>::T> berlekamp_massey(zc V<zy Poly<MOD>::T>&s){
zd Poly<MOD> P;zd zy P::T T;zd zy P::O O;V<T>C(1,1),B(1,1);int L=0,m=1;T b=1;
for(S n=0;n<s.size();n++){T d=s[n];for(int i=1;i<=L;i++)d=O::add(d,O::mul(C[i],s[n-i]));if(!d){++m;continue;}T coef=O::mul(d,O::inv(b));V<T>Tc=C;if(C.size()<B.size()+m)C.resize(B.size()+m);for(S j=0;j<B.size();j++)C[j+m]=O::sub(C[j+m],O::mul(coef,B[j]));if(2*L<=(int)n){L=(int)n+1-L;B=Tc;b=d;m=1;}else ++m;}C.erase(C.begin());for(T&x:C)x=O::neg(x);zr C;
}
zt<u64 MOD> zy Poly<MOD>::T bostan_mori(Poly<MOD> p,Poly<MOD> q,u64 k){
zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;assert(!q.empty()&&q.a[0]);
while(k){P qm=q;for(S i=1;i<qm.size();i+=2)qm.a[i]=O::neg(qm.a[i]);P s=p*qm,t=q*qm;V<T>np,nq;np.reserve((s.size()+1)/2);nq.reserve((t.size()+1)/2);for(S i=k&1;i<s.size();i+=2)np.push_back(s.a[i]);for(S i=0;i<t.size();i+=2)nq.push_back(t.a[i]);p=P(np);q=P(nq);k>>=1;}zr O::mul(p.empty()?0:p.a[0],O::inv(q.a[0]));
}
zt<u64 MOD> Poly<MOD> poly_gcd(Poly<MOD>a,Poly<MOD>b){zd zy Poly<MOD>::O O;while(!b.empty()){a%=b;std::swap(a,b);}if(!a.empty())a/=a.a.back();zr a;}
zt<u64 MOD> std::tuple<Poly<MOD>,Poly<MOD>,Poly<MOD> > poly_exgcd(Poly<MOD>a,Poly<MOD>b){zd Poly<MOD>P;P x0{1},x1,y0,y1{1};while(!b.empty()){auto qr=a.divmod(b);P nx=x0-qr.first*x1,ny=y0-qr.first*y1;a=b;b=qr.second;x0=x1;x1=nx;y0=y1;y1=ny;}if(!a.empty()){auto c=P::O::inv(a.a.back());a*=c;x0*=c;y0*=c;}zr std::make_tuple(a,x0,y0);}
zt<u64 MOD> zy Poly<MOD>::T resultant(Poly<MOD>a,Poly<MOD>b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;if(a.empty()||b.empty())zr 0;T ans=1;if(a.deg()<b.deg()){if((a.deg()*b.deg())&1)ans=O::neg(ans);std::swap(a,b);}for(;;){if(b.deg()==0)zr O::mul(ans,O::pw(b.a[0],a.deg()));P r=a%b;if(r.empty())zr 0;if((a.deg()*b.deg())&1)ans=O::neg(ans);ans=O::mul(ans,O::pw(b.a.back(),(u64)(a.deg()-r.deg())));a=b;b=r;}}
zt<u64 MOD> zy Poly<MOD>::T linear_nth(zc V<zy Poly<MOD>::T>&init,zc V<zy Poly<MOD>::T>&rec,u64 k){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;if(k<init.size())zr init[(S)k];S d=rec.size();assert(init.size()>=d&&d);P q(d+1);q.a[0]=1;for(S i=0;i<d;i++)q.a[i+1]=O::neg(rec[i]);P p=(P(V<T>(init.begin(),init.begin()+d))*q).pre(d);zr bostan_mori(p,q,k);}
zt<u64 MOD> void fwt_or(V<zy Poly<MOD>::T>&a,bool inv=false){zd zy Poly<MOD>::O O;for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++)a[i+j+l]=inv?O::sub(a[i+j+l],a[i+j]):O::add(a[i+j+l],a[i+j]);}
zt<u64 MOD> void fwt_and(V<zy Poly<MOD>::T>&a,bool inv=false){zd zy Poly<MOD>::O O;for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++)a[i+j]=inv?O::sub(a[i+j],a[i+j+l]):O::add(a[i+j],a[i+j+l]);}
zt<u64 MOD> void fwt_xor(V<zy Poly<MOD>::T>&a,bool inv=false){zd Poly<MOD>P;zd zy P::O O;zy P::T h=inv?O::inv(O::norm(2)):O::norm(1);for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++){auto x=a[i+j],y=a[i+j+l];a[i+j]=O::mul(O::add(x,y),h);a[i+j+l]=O::mul(O::sub(x,y),h);}}
zt<u64 MOD,int TYPE> V<zy Poly<MOD>::T> bitwise_convolution(V<zy Poly<MOD>::T>a,V<zy Poly<MOD>::T>b){assert(a.size()==b.size()&&!a.empty()&&!(a.size()&(a.size()-1)));if(TYPE==0)fwt_or<MOD>(a),fwt_or<MOD>(b);else if(TYPE==1)fwt_and<MOD>(a),fwt_and<MOD>(b);else fwt_xor<MOD>(a),fwt_xor<MOD>(b);for(S i=0;i<a.size();i++)a[i]=Poly<MOD>::O::mul(a[i],b[i]);if(TYPE==0)fwt_or<MOD>(a,1);else if(TYPE==1)fwt_and<MOD>(a,1);else fwt_xor<MOD>(a,1);zr a;}
zt<u64 MOD> zy Poly<MOD>::T lagrange_consecutive(zc V<zy Poly<MOD>::T>&y,zy Poly<MOD>::T x){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S n=y.size();if(!n)zr 0;V<T>pre(n+1),suf(n+1),fac(n),ifac(n);pre[0]=suf[n]=fac[0]=1;for(S i=0;i<n;i++)pre[i+1]=O::mul(pre[i],O::sub(x,O::norm((u64)i)));for(S i=n;i--;)suf[i]=O::mul(suf[i+1],O::sub(x,O::norm((u64)i)));for(S i=1;i<n;i++)fac[i]=O::mul(fac[i-1],O::norm((u64)i));ifac[n-1]=O::inv(fac[n-1]);for(S i=n-1;i;i--)ifac[i-1]=O::mul(ifac[i],O::norm((u64)i));T ans=0;for(S i=0;i<n;i++){T v=O::mul(y[i],O::mul(pre[i],suf[i+1]));v=O::mul(v,O::mul(ifac[i],ifac[n-1-i]));if((n-1-i)&1)v=O::neg(v);ans=O::add(ans,v);}zr ans;}
zt<u64 MOD> V<zy Poly<MOD>::T> subset_convolution(zc V<zy Poly<MOD>::T>&a,zc V<zy Poly<MOD>::T>&b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S N=a.size();assert(N==b.size()&&N&&!(N&(N-1)));int k=__builtin_ctzll(N);V<T>A((k+1)*N),B((k+1)*N),C((k+1)*N);for(S s=0;s<N;s++){int r=__builtin_popcountll(s);A[(S)r*N+s]=a[s];B[(S)r*N+s]=b[s];}for(int r=0;r<=k;r++)for(int bit=0;bit<k;bit++)for(S s=0;s<N;s++)if(s&(S(1)<<bit)){A[(S)r*N+s]=O::add(A[(S)r*N+s],A[(S)r*N+(s^(S(1)<<bit))]);B[(S)r*N+s]=O::add(B[(S)r*N+s],B[(S)r*N+(s^(S(1)<<bit))]);}for(S s=0;s<N;s++)for(int r=0;r<=k;r++)for(int i=0;i<=r;i++)C[(S)r*N+s]=O::add(C[(S)r*N+s],O::mul(A[(S)i*N+s],B[(S)(r-i)*N+s]));for(int r=0;r<=k;r++)for(int bit=0;bit<k;bit++)for(S s=0;s<N;s++)if(s&(S(1)<<bit))C[(S)r*N+s]=O::sub(C[(S)r*N+s],C[(S)r*N+(s^(S(1)<<bit))]);V<T>res(N);for(S s=0;s<N;s++)res[s]=C[(S)__builtin_popcountll(s)*N+s];zr res;}
zt<u64 MOD> V<zy Poly<MOD>::T> dirichlet_convolution(zc V<zy Poly<MOD>::T>&a,zc V<zy Poly<MOD>::T>&b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S n=std::min(a.size(),b.size());V<T>c(n);for(S i=1;i<n;i++)for(S j=1;i*j<n;j++)c[i*j]=O::add(c[i*j],O::mul(a[i],b[j]));zr c;}
inline V<u32> convolution_mod(zc V<u32>&a,zc V<u32>&b,u32 M){
if(a.empty()||b.empty())zr{};if(M==1)zr V<u32>(a.size()+b.size()-1);if(M==998244353u)zr pd::N1::conv(a,b);if(M==754974721u)zr pd::N2::conv(a,b);if(M==469762049u)zr pd::N3::conv(a,b);if(M==167772161u)zr pd::N4::conv(a,b);if(M==1224736769u)zr pd::N5::conv(a,b);if(std::min(a.size(),b.size())<=24){V<u32>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=(c[i+j]+(u64)(a[i]%M)*(b[j]%M))%M;zr c;}auto x=pd::N1::conv(a,b),y=pd::N2::conv(a,b),z=pd::N3::conv(a,b);V<u32>c(x.size());zs zc u64 i12=pd::I64(pd::P1%pd::P2,pd::P2),i123=pd::I64((u128)pd::P1*pd::P2%pd::P3,pd::P3);u64 q1=pd::P1%M,q12=q1*(pd::P2%M)%M;for(S i=0;i<c.size();i++){u64 t2=(u64)((y[i]+pd::P2-x[i]%pd::P2)%pd::P2)*i12%pd::P2,X=(u64)x[i]+pd::P1*t2,t3=(u64)((z[i]+pd::P3-X%pd::P3)%pd::P3)*i123%pd::P3,r=x[i]%M;r=(r+q1*(t2%M))%M;r=(r+q12*(t3%M))%M;c[i]=(u32)r;}zr c;
}
#undef zr
#undef zs
#undef zc
#undef zt
#undef zy
#undef zd
#undef zf
#endif
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define fst first
#define sed second
#define pref static inline
using namespace std;using hint=__int128;using uhint=unsigned __int128;
using us=unsigned short;using ui=unsigned int;using ll=long long;using ull=unsigned long long;
using db=double;using ldb=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;
using pil=pair<int,ll>;using pli=pair<ll,int>;using vi=vector<int>;using vl=vector<ll>;
using vpi=vector<pii>;using vpl=vector<pll>;using vpil=vector<pil>;using vpli=vector<pli>;
ostream& out128(ostream&,uhint,bool);ostream& operator<<(ostream&,hint);ostream& operator<<(ostream&,uhint);
namespace mystl{
const int SI=1<<22,SO=1<<20;pref size_t fr(void*p,size_t n){
#ifdef __linux__
return fread_unlocked(p,1,n,stdin);
#else
return fread(p,1,n,stdin);
#endif
}
unsigned char mp[1<<16];struct Init{Init(){memset(mp,255,sizeof mp);for(unsigned i=0;i<10;++i)for(unsigned j=0;j<10;++j){unsigned char s[2]={static_cast<unsigned char>('0'+i),static_cast<unsigned char>('0'+j)};uint16_t x;memcpy(&x,s,2);mp[x]=static_cast<unsigned char>(i*10+j);}}}init;
pref unsigned pv(const char*p){uint16_t x;memcpy(&x,p,2);return mp[x];}
struct IB:streambuf{
char b[SI];bool eofed=false;IB(){setg(b,b,b);}
int_type underflow()override{if(gptr()<egptr())return traits_type::to_int_type(*gptr());size_t n=fr(b,SI);if(!n)return traits_type::eof();setg(b,b,b+n);return traits_type::to_int_type(*gptr());}
inline void commit(char*p){gbump(static_cast<int>(p-gptr()));}
inline bool refill(char*&p,char*&e){commit(p);if(traits_type::eq_int_type(underflow(),traits_type::eof())){eofed=true;return false;}p=gptr();e=egptr();return true;}
inline bool head(char*&p,char*&e,bool&neg){eofed=false;for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}neg=false;if(*p=='-'||*p=='+'){neg=*p=='-';++p;if(p==e&&!refill(p,e))return false;}return true;}
template<class T,class U>inline bool slow(T&x,bool neg,char*&p,char*&e){U y=0;bool ok=false;for(;;){while(p<e){unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c>9){commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}ok=true;y=static_cast<U>(y*10+c);++p;}if(!refill(p,e)){if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}}}
template<class T,class U,int K>inline bool num(T&x){x=0;char*p=gptr(),*e=egptr();bool neg;if(!head(p,e,neg))return false;if(e-p<2*K+1)return slow<T,U>(x,neg,p,e);U y=0;bool ok=false;for(int i=0;i<K;++i){unsigned v=pv(p);if(v>=255)break;ok=true;y=static_cast<U>(y*100+static_cast<U>(v));p+=2;}unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c<=9){ok=true;y=static_cast<U>(y*10+c);++p;}commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}
inline bool read(short&x){return num<short,unsigned short,5>(x);}inline bool read(us&x){return num<us,us,5>(x);}inline bool read(int&x){return num<int,unsigned,5>(x);}inline bool read(unsigned&x){return num<unsigned,unsigned,5>(x);}inline bool read(long&x){return sizeof(long)<=4?num<long,unsigned long,5>(x):num<long,unsigned long,10>(x);}inline bool read(unsigned long&x){return sizeof(unsigned long)<=4?num<unsigned long,unsigned long,5>(x):num<unsigned long,unsigned long,10>(x);}inline bool read(ll&x){return num<ll,ull,10>(x);}inline bool read(ull&x){return num<ull,ull,10>(x);}inline bool read(hint&x){return num<hint,uhint,20>(x);}inline bool read(uhint&x){return num<uhint,uhint,20>(x);}
inline bool read(char&x){x=0;eofed=false;char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e){x=*p++;commit(p);return true;}if(!refill(p,e))return false;}}
inline bool read(string&x){eofed=false;x.clear();char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}for(;;){char*q=p;while(q<e&&static_cast<unsigned char>(*q)>32)++q;x.append(p,static_cast<size_t>(q-p));p=q;if(p<e){commit(p);return true;}if(!refill(p,e))return true;}}
template<class T>inline bool fp(T&x){x=0;string s;if(!read(s))return false;return cv(s.c_str(),x);}static inline bool cv(const char*s,float&x){char*e=nullptr;x=strtof(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,double&x){char*e=nullptr;x=strtod(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,long double&x){char*e=nullptr;x=strtold(s,&e);return e!=s&&*e==0;}
}ib;
struct OB:streambuf{
char b[SO];OB(){setp(b,b+SO);}~OB(){sync();}
int sync()override{size_t n=static_cast<size_t>(pptr()-pbase());if(n&&fwrite(b,1,n,stdout)!=n)return -1;setp(b,b+SO);return 0;}
int_type overflow(int_type c=traits_type::eof())override{if(sync())return traits_type::eof();if(!traits_type::eq_int_type(c,traits_type::eof()))*pptr()=traits_type::to_char_type(c),pbump(1);return traits_type::not_eof(c);}
inline void pc(char c){if(pptr()==epptr()&&traits_type::eq_int_type(overflow(),traits_type::eof()))return;*pptr()=c;pbump(1);}inline void ps(const char*s,size_t n){while(n){size_t k=static_cast<size_t>(epptr()-pptr());if(!k){if(traits_type::eq_int_type(overflow(),traits_type::eof()))return;k=static_cast<size_t>(epptr()-pptr());}k=min(k,n);memcpy(pptr(),s,k);pbump(static_cast<int>(k));s+=k;n-=k;}}
}ob;
struct FastIn:istream{
FastIn():istream(&ib){}using istream::operator>>;template<class T>inline FastIn&go(T&x){if(!ib.read(x))setstate(ib.eofed?ios::eofbit|ios::failbit:ios::failbit);else if(ib.eofed)setstate(ios::eofbit);return *this;}inline FastIn&operator>>(short&x){return go(x);}inline FastIn&operator>>(us&x){return go(x);}inline FastIn&operator>>(int&x){return go(x);}inline FastIn&operator>>(unsigned&x){return go(x);}inline FastIn&operator>>(long&x){return go(x);}inline FastIn&operator>>(unsigned long&x){return go(x);}inline FastIn&operator>>(ll&x){return go(x);}inline FastIn&operator>>(ull&x){return go(x);}inline FastIn&operator>>(hint&x){return go(x);}inline FastIn&operator>>(uhint&x){return go(x);}inline FastIn&operator>>(char&x){return go(x);}inline FastIn&operator>>(string&x){return go(x);}inline FastIn&operator>>(float&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(long double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(bool&x){int y=0;go(y);x=y!=0;return *this;}
}fin;
struct FastOut:ostream{
FastOut():ostream(&ob){}using ostream::operator<<;template<class U>inline FastOut&uo(U x){char s[64];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);while(n)ob.pc(s[--n]);return *this;}template<class T>inline FastOut&so(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}typedef typename make_unsigned<T>::type U;U y;if(x<0){ob.pc('-');y=U(0)-static_cast<U>(x);}else y=static_cast<U>(x);return uo(y);}template<class T>inline FastOut&un(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}
inline FastOut&operator<<(short x){return so(x);}inline FastOut&operator<<(us x){return un(x);}inline FastOut&operator<<(int x){return so(x);}inline FastOut&operator<<(unsigned x){return un(x);}inline FastOut&operator<<(long x){return so(x);}inline FastOut&operator<<(unsigned long x){return un(x);}inline FastOut&operator<<(ll x){return so(x);}inline FastOut&operator<<(ull x){return un(x);}inline FastOut&operator<<(bool x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}ob.pc(x?'1':'0');return *this;}inline FastOut&operator<<(char c){if(width()!=0){static_cast<ostream&>(*this)<<c;return *this;}ob.pc(c);return *this;}inline FastOut&operator<<(const char*s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s,strlen(s));return *this;}inline FastOut&operator<<(const string&s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s.data(),s.size());return *this;}inline FastOut&operator<<(float x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(double x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(long double x){static_cast<ostream&>(*this)<<x;return *this;}
inline FastOut&operator<<(hint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}uhint y;if(x<0){ob.pc('-');y=uhint(0)-static_cast<uhint>(x);}else y=static_cast<uhint>(x);return uo(y);}inline FastOut&operator<<(uhint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}FastOut&operator<<(ios_base&(*f)(ios_base&)){f(*this);return *this;}FastOut&operator<<(ostream&(*f)(ostream&)){f(*this);return *this;}FastOut&operator<<(ios&(*f)(ios&)){f(*this);return *this;}
}fout;
}
ostream& out128(ostream&out,uhint x,bool neg){char s[48];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);streamsize w=out.width(0),k=max<streamsize>(0,w-n-neg);char f=out.fill();ios::fmtflags a=out.flags()&ios::adjustfield;if(a==ios::left){if(neg)out.put('-');while(n)out.put(s[--n]);while(k--)out.put(f);}else if(a==ios::internal&&neg){out.put('-');while(k--)out.put(f);while(n)out.put(s[--n]);}else{while(k--)out.put(f);if(neg)out.put('-');while(n)out.put(s[--n]);}return out;}
ostream& operator<<(ostream&out,hint x){bool neg=x<0;return out128(out,neg?uhint(0)-static_cast<uhint>(x):static_cast<uhint>(x),neg);}ostream& operator<<(ostream&out,uhint x){return out128(out,x,false);}
#define cin mystl::fin
#define cout mystl::fout
namespace my{
using poly=vector<ull>;
ull P;
int B;
pref ull mul(ull a,ull b,ull p){
return (u128)a*b%p;
}
pref ull power(ull a,ull b,ull p){
ull ans=1;
while(b){
if(b&1)ans=mul(ans,a,p);
a=mul(a,a,p),b>>=1;
}
return ans;
}
pref ull gcd(ull a,ull b){
while(b){
ull t=a%b;
a=b,b=t;
}
return a;
}
bool prime(ull n){
if(n<2)return false;
for(int p:{2,3,5,7,11,13,17,19,23,29,31,37})
if(n%p==0)return n==(ull)p;
ull d=n-1;
int s=0;
while(!(d&1))d>>=1,s++;
for(ull a:{2ull,325ull,9375ull,28178ull,450775ull,9780504ull,1795265022ull}){
if(a%n==0)continue;
ull x=power(a%n,d,n);
if(x==1||x==n-1)continue;
bool ok=false;
up(i,1,s-1){
x=mul(x,x,n);
if(x==n-1){
ok=true;
break;
}
}
if(!ok)return false;
}
return true;
}
pref void trim(poly&a){
while(!a.empty()&&!a.back())a.pop_back();
}
template<u32 M,u32 G>struct Cntt{
using NT=pd::NTT<M,G>;
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
__attribute__((target("avx2"))) static vector<u32> fast(vector<u32>a,vector<u32>b){
using A=pd::AN<M,G>;
int n=a.size(),l=__builtin_ctz((u32)n);
A::fw2(l,a.data(),b.data());
for(int i=0;i<n;i+=8)
A::st(a.data()+i,A::mv(A::ld(a.data()+i),A::ld(b.data()+i),false));
A::iv(l,a.data(),A::rr().r);
for(auto&x:a)if(x>=M)x-=M;
return a;
}
#endif
static vector<u32> run(const poly&a,const poly&b,int n){
vector<u32>x(n),y(n);
up(i,0,(int)a.size()-1)x[i]=a[i]%M;
up(i,0,(int)b.size()-1)y[i]=b[i]%M;
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(NT::avx()&&n>=8)return fast(move(x),move(y));
#endif
NT::ntt(x,0),NT::ntt(y,0);
up(i,0,n-1)x[i]=NT::mul(x[i],y[i]);
NT::ntt(x,1);
return x;
}
};
poly conv(const poly&a,const poly&b,int len=0,int mode=0){
if(a.empty()||b.empty())return {};
int n=a.size(),m=b.size(),sz=len?len:n+m-1;
poly c(sz);
if(min(n,m)<=24){
up(k,0,n+m-2){
u128 v=0;
up(i,max(0,k-m+1),min(k,n-1))v+=(u128)a[i]*b[k-i];
if(len){ull &x=c[k&(len-1)];x+=v%P;if(x>=P)x-=P;}
else c[k]=v%P;
}
return c;
}
int cap=1;
while(cap<sz)cap<<=1;
auto a0=Cntt<998244353,3>::run(a,b,cap);
auto a1=Cntt<754974721,11>::run(a,b,cap);
auto a2=Cntt<469762049,3>::run(a,b,cap);
auto a3=Cntt<167772161,3>::run(a,b,cap);
auto a4=Cntt<880803841,26>::run(a,b,cap);
ull w1=998244353ull%P,w2=(u128)w1*754974721%P;
ull w3=(u128)w2*469762049%P,w4=(u128)w3*167772161%P;
up(i,0,sz-1){
ull d0=a0[i];
ull d1=a1[i];
d1=(d1+754974721-d0%754974721)*416537774%754974721;
ull d2=a2[i];
d2=(d2+469762049-d0%469762049)*208783132%469762049;
d2=(d2+469762049-d1%469762049)*221064492%469762049;
ull d3=a3[i];
d3=(d3+167772161-d0%167772161)*47450712%167772161;
d3=(d3+167772161-d1%167772161)*95869806%167772161;
d3=(d3+167772161-d2%167772161)*130489458%167772161;
ull d4=a4[i];
d4=(d4+880803841-d0%880803841)*440401913%880803841;
d4=(d4+880803841-d1%880803841)*7%880803841;
d4=(d4+880803841-d2%880803841)*754974723%880803841;
d4=(d4+880803841-d3%880803841)*621743889%880803841;
c[i]=(d0+(u128)w1*d1+(u128)w2*d2+(u128)w3*d3+(u128)w4*d4)%P;
}
return c;
}
poly fac,ifac;
ull shift(const poly&a,ull x,int m,poly&ans){
int d=(int)a.size()-1,len=d+m;
poly v(len),pre(len+1),iv(len),w(d+1);
ull z=(x+P-d)%P;
pre[0]=1;
up(i,0,len-1){
v[i]=z;
pre[i+1]=mul(pre[i],z,P);
if(++z==P)z=0;
}
if(gcd(pre[len],P)!=1){
for(ull x:v){
ull g=gcd(x,P);
if(g>1&&g<P)return g;
}
}
ull t=pd::I64(pre[len],P);
dn(i,len-1,0){
iv[i]=mul(t,pre[i],P);
t=mul(t,v[i],P);
}
up(i,0,d){
w[i]=mul(mul(a[i],ifac[i],P),ifac[d-i],P);
if((d-i)&1)w[i]=w[i]?P-w[i]:0;
}
int cap=1;
while(cap<len)cap<<=1;
poly c=conv(w,iv,cap);
ans.resize(m);
t=pre[d+1];
up(i,0,m-1){
ans[i]=mul(t,c[d+i],P);
if(i+1<m)t=mul(mul(t,v[d+i+1],P),iv[i],P);
}
return 0;
}
ull factor(ull n){
P=n,B=8;
while((u128)B*B*B*B*900<(u128)n*64)B<<=1;
ull span=(ull)B*30/8;
const int rs[8]={1,7,11,13,17,19,23,29};
up(i,2,2*B+2)if(n%i==0)return i;
fac.resize(B+1),ifac.resize(B+1);
fac[0]=1;
up(i,1,B)fac[i]=mul(fac[i-1],i,P);
ifac[B]=pd::I64(fac[B],P);
dn(i,B,1)ifac[i-1]=mul(ifac[i],i,P);
ull ib=pd::I64(B,P);
poly f(9,1);
up(i,0,8)for(int r:rs)f[i]=mul(f[i],(i*span+r)%P,P);
for(int d=8;d<B;d<<=1){
poly a,b;
ull g=shift(f,d+1,d,a);
if(g)return g;
g=shift(f,mul(d,ib,P),2*d+1,b);
if(g)return g;
f.resize(2*d+1);
up(i,0,d-1)f[d+1+i]=a[i];
up(i,0,2*d)f[i]=mul(f[i],b[i],P);
}
up(i,0,B-1){
ull g=gcd(f[i],P);
if(g>1&&g<P)return g;
if(g==P){
up(j,0,B/8-1)for(int r:rs){
g=gcd(i*span+30ull*j+r,P);
if(g>1&&g<P)return g;
}
}
}
return 0;
}
ull solve(ull n){
ull ans=0;
up(p,2,100)if(n%p==0){
ans=p;
while(n%p==0)n/=p;
}
if(n==1)return ans;
if(prime(n))return max(ans,n);
ull r=sqrtl((long double)n);
while((u128)r*r>n)--r;
while((u128)(r+1)*(r+1)<=n)++r;
if((u128)r*r==n)return max(ans,solve(r));
r=cbrtl((long double)n);
while((u128)r*r*r>n)--r;
while((u128)(r+1)*(r+1)*(r+1)<=n)++r;
if((u128)r*r*r==n)return max(ans,solve(r));
ull p=factor(n);
return max(ans,max(solve(p),solve(n/p)));
}
pref void SOLVE(){
ull n;cin>>n;
if(prime(n))cout<<"Prime\n";
else cout<<solve(n)<<'\n';
}
}
int main(){
int T;cin>>T;
while(T--)my::SOLVE();
return 0;
}:::
搞笑的是，那位大人一卡常直接又快了三倍，吓哭了。
:::success[AC code 9.69s]
//Author:kevinZ99
#ifndef KEVIN_POLY_ALL_HPP
#define KEVIN_POLY_ALL_HPP
#include <bits/stdc++.h>
#define zr return
#define zs static
#define zc const
#define zt template
#define zy typename
#define zd typedef
#define zf friend
zt<class T>using V=std::vector<T>;zt<class A,class B>using Q=std::pair<A,B>;using S=std::size_t;using u32=uint32_t;using u64=uint64_t;using u128=__uint128_t;using i128=__int128_t;
#ifndef PI
#define PI inline __attribute__((always_inline))
#endif
namespace pd{
zt<class T>struct SE:std::is_signed<T>{};zt<>struct SE<i128>:std::true_type{};zt<>struct SE<u128>:std::false_type{};PI u64 M64(u64 a,u64 b,u64 m){zr(u128)a*b%m;}PI u64 I64(u64 a,u64 m){
if(m==0){
assert(a&1);u64 x=a;for(int i=0;i<6;i++)x*=2-a*x;zr x;}i128 t=0,nt=1;u64 r=m,nr=a%m;while(nr){u64 q=r/nr,rr=r-q*nr;r=nr;nr=rr;i128 tt=t-(i128)q*nt;t=nt;nt=tt;}assert(r==1);if(t<0)t+=m;zr(u64)t;}zt<u64 MOD> struct CT{zd zy std::conditional<(MOD!=0 && MOD<=0xffffffffULL),u32,u64>::type type;};zt<u64 MOD> struct MO{
zd zy CT<MOD>::type T;zt<class U> zs PI T norm(U x){zr norm_impl(x,zy SE<U>::type());}zt<class U> zs PI T norm_impl(U x,std::true_type){
if(MOD==0)zr(T)(u64)x;i128 y=(i128)x%(i128)MOD;if(y<0)y+=MOD;zr(T)y;}zt<class U> zs PI T norm_impl(U x,std::false_type){zr MOD?(T)((u128)x%MOD):(T)(u64)x;}zs PI T add(T a,T b){
if(MOD==0)zr(T)(a+b);if(MOD<=0xffffffffULL){u64 s=(u64)a+b;if(s>=MOD)s-=MOD;zr(T)s;}u64 s=a+b;if(s<a || s>=MOD)s-=MOD;zr s;}zs PI T sub(T a,T b){if(MOD==0)zr(T)(a-b);zr a>=b?a-b:(T)(MOD-(u64)b+a);}zs PI T neg(T a){zr a?(MOD?T(MOD-a):T(0-a)):0;}zs PI T mul(T a,T b){if(MOD==0)zr(T)(a*b);if(MOD<=0xffffffffULL)zr(T)((u64)a*b%MOD);zr(T)((u128)a*b%MOD);}zs PI T inv(T a){zr(T)I64((u64)a,MOD);}zs PI T pw(T a,u64 e){T r=norm(1);for(;e;e>>=1,a=mul(a,a))if(e&1)r=mul(r,a);zr r;}};
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
#include <immintrin.h>
using X=__m256i;
#define PA __attribute__((target("avx2")))
#define PVL(x) _mm256_loadu_si256((const X*)(x))
#define PVS(x,v) _mm256_storeu_si256((X*)(x),v)
#define V0 _mm256_sub_epi32
#define V1 _mm256_add_epi32
#define V2 _mm256_setr_epi32
#define V3 _mm256_mul_epu32
#define V4 _mm256_blend_epi32
#define V5 _mm256_shuffle_epi32
#define V6 _mm256_set1_epi32
#define V7 _mm256_permutevar8x32_epi32
#define V8 _mm256_min_epu32
#define V9 _mm256_srli_epi64
#define VA _mm256_set1_epi64x
#define VB _mm256_permute4x64_epi64
#define VC _mm256_add_epi64
#define VD _mm256_set_epi64x
#define VE _mm256_permute2x128_si256
#define VF _mm256_or_si256
#define VG _mm256_srli_si256
#define VH _mm256_slli_epi64
zt<u32 P,u32 G>struct AN{
zs PI u32 sm(u32 a,u32 b){zr(u64)a*b%P;}zs u32 pw(u32 a,u32 e){u32 x=1;for(;e;e>>=1,a=sm(a,a))if(e&1)x=sm(x,a);zr x;}zs u32 ni32(){u32 x=1;for(int i=0;i<5;i++)x*=2-P*x;zr 0u-x;}
struct R{u32 ni,r,r2,w[4],wr[4];u64 wd[30][4],wid[30][4];u32 wl[30][8],wil[30][8];R(){ni=ni32();r=(u64(1)<<32)%P;r2=(u64)r*r%P;int l=__builtin_ctz(P-1);u32 x[31]={},y[31]={};x[l]=tm(pw(G,(P-1)>>l));y[l]=tm(pw(pw(G,(P-1)>>l),P-2));for(int i=l-1;i>=0;i--)x[i]=mm(x[i+1],x[i+1]),y[i]=mm(y[i+1],y[i+1]);w[0]=wr[0]=r;if(l>=2){w[1]=x[2];wr[1]=y[2];if(l>=3)w[2]=x[3],wr[2]=y[3],w[3]=mm(w[1],w[2]),wr[3]=mm(wr[1],wr[2]);}u32 a=r,b=r;for(int i=0;i<l-2;i++){u32 f=mm(a,x[i+3]),g=mm(b,y[i+3]);a=mm(a,y[i+3]);b=mm(b,x[i+3]);u32 f2=mm(f,f),g2=mm(g,g);u64 A[4]={f2,f,f2,f},B[4]={g2,g,g2,g};memcpy(wd[i],A,32);memcpy(wid[i],B,32);}a=b=r;for(int i=0;i<l-3;i++){u32 f=mm(a,x[i+4]),g=mm(b,y[i+4]);a=mm(a,y[i+4]);b=mm(b,x[i+4]);u32 f2=mm(f,f),f3=mm(f2,f2),g2=mm(g,g),g3=mm(g2,g2);u32 A[8]={f,f,f,f,f2,f2,f3,r},B[8]={g,g,g,g,g2,g2,g3,r};memcpy(wl[i],A,32);memcpy(wil[i],B,32);}}u32 rd(u64 x)zc{u32 m=(u32)x*ni,v=(u32)((x+(u64)m*P)>>32);zr v>=P?v-P:v;}u32 mm(u32 a,u32 b)zc{zr rd((u64)a*b);}u32 tm(u32 x)zc{zr mm(x,r2);}};
zs R&rr(){zs R x;zr x;}PA zs X ld(zc u32*x){zr PVL(x);}PA zs void st(u32*x,X v){PVS(x,v);}PA zs X sh(X x){X p=V6(P);zr V8(x,V0(x,p));}PA zs X ad(X a,X b){zr sh(V1(a,b));}PA zs X su(X a,X b){X d=V0(a,b);zr V8(d,V1(d,V6(P)));}
PA zs X mv(X a,X b,bool strict=true){R&q=rr();X ni=VA((u64)q.ni),p=VA(P),e=V3(a,b),o=V3(V9(a,32),V9(b,32));e=V9(VC(e,V3(V3(e,ni),p)),32);o=V9(VC(o,V3(V3(o,ni),p)),32);X z=VF(e,VH(o,32));zr strict?sh(z):z;}
PA zs X me(X a,X b,bool strict=true){R&q=rr();X ni=VA((u64)q.ni),p=VA(P),as=VG(a,4),e=V3(a,b),o=V3(as,b);e=VC(e,V3(V3(e,ni),p));o=VC(o,V3(V3(o,ni),p));X z=VF(VG(e,4),o);zr strict?sh(z):z;}
PA zs X h2(X x){X m=V6(P*2);zr V8(x,V0(x,m));}PA zs void hb(X a,X t,X&x,X&y){a=h2(a);x=V1(a,t);y=V0(V1(a,V6(P*2)),t);}PA zs void hi(X a,X b,X&x,X&y){a=h2(a);b=h2(b);x=V1(a,b);y=V0(V1(a,V6(P*2)),b);}zt<bool I,bool T>PA zs void b4(u32*a,u32*b,u32*c,u32*d,X w1,X w2,X w3){X A=sh(h2(ld(a))),B=sh(h2(ld(b))),C=sh(h2(ld(c))),D=sh(h2(ld(d)));if(!I){if(!T)C=mv(C,w1,false);{X x,y;hb(A,C,x,y);A=x;C=y;}if(!T)D=mv(D,w1,false);{X x,y;hb(B,D,x,y);B=x;D=y;}if(!T)B=me(B,w2,false);{X x,y;hb(A,B,x,y);A=x;B=y;}D=me(D,w3,false);{X x,y;hb(C,D,x,y);C=x;D=y;}}else{{X x,y;hi(A,B,x,y);if(!T)y=me(y,w2,false);A=x;B=y;}{X x,y;hi(C,D,x,y);y=me(y,w3,false);C=x;D=y;}{X x,y;hi(A,C,x,y);if(!T)y=mv(y,w1,false);A=x;C=y;}{X x,y;hi(B,D,x,y);if(!T)y=mv(y,w1,false);B=x;D=y;}}st(a,A);st(b,B);st(c,C);st(d,D);}
zt<bool I,bool T>PA zs void ax(int k,int o,u32*d,X&w){X w1=V5(w,0),w2=VB(w,0x55),w3=VB(w,0xff);int q=1<<k;for(int j=0;j<q;j+=8)b4<I,T>(d+o+j,d+o+q+j,d+o+2*q+j,d+o+3*q+j,w1,w2,w3);int z=__builtin_ctz(~(u32)o>>(k+2));w=mv(w,ld((u32*)(I?rr().wid[z]:rr().wd[z])));}
PA zs void lo(u32*d,X w0,X w1,X w2,X M){X v=ld(d);v=mv(v,w0,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w1,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w2,false);X x=V1(V4(v,V0(M,v),0xaa),V5(v,0xb1));st(d,V8(x,V0(x,M)));}
zt<bool T>PA zs void ax2(int k,int o,u32*a,u32*b,X&w){X w1=V5(w,0),w2=VB(w,0x55),w3=VB(w,0xff);int q=1<<k;for(int j=0;j<q;j+=8){b4<0,T>(a+o+j,a+o+q+j,a+o+2*q+j,a+o+3*q+j,w1,w2,w3);b4<0,T>(b+o+j,b+o+q+j,b+o+2*q+j,b+o+3*q+j,w1,w2,w3);}int z=__builtin_ctz(~(u32)o>>(k+2));w=mv(w,ld((u32*)rr().wd[z]));}
PA zs void fw2(int l,u32*a,u32*b){R&q=rr();if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(ld(a+j)),B=sh(ld(a+s+j)),C=sh(ld(b+j)),D=sh(ld(b+s+j));st(a+j,ad(A,B));st(a+s+j,su(A,B));st(b+j,ad(C,D));st(b+s+j,su(C,D));}}for(int k=l-2-(!(l&1));k>=3;k-=2){X w=VD(q.w[1],q.w[0],q.w[0],q.w[0]);ax2<1>(k,0,a,b,w);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax2<0>(k,i,a,b,w);}X w=V2(q.w[0],q.w[1],q.w[2],q.w[3],q.w[0],q.w[1],q.w[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C);lo(a+i,w0,w1,w2,M);lo(b+i,w0,w1,w2,M);if(i+8<(1<<l))w=mv(w,ld(q.wl[__builtin_ctz(~(u32)i>>3)]));}}
PA zs void fw(int l,u32*d){R&q=rr();if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(ld(d+j)),B=sh(ld(d+s+j));st(d+j,ad(A,B));st(d+s+j,su(A,B));}}for(int k=l-2-(!(l&1));k>=3;k-=2){X w=VD(q.w[1],q.w[0],q.w[0],q.w[0]);ax<0,1>(k,0,d,w);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax<0,0>(k,i,d,w);}X w=V2(q.w[0],q.w[1],q.w[2],q.w[3],q.w[0],q.w[1],q.w[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C),v=ld(d+i);v=mv(v,w0,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w1,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w2,false);v=V8(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),V0(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),M));st(d+i,v);if(i+8<(1<<l))w=mv(w,ld(q.wl[__builtin_ctz(~(u32)i>>3)]));}}
PA zs void iv(int l,u32*d,u32 ex=0){R&q=rr();X w=V2(q.wr[0],q.wr[1],q.wr[2],q.wr[3],q.wr[0],q.wr[1],q.wr[0],q.r);zc X A=V2(7,7,7,7,6,6,6,6),B=V2(7,7,4,4,7,7,5,5),C=V2(7,0,7,1,7,2,7,3),M=V6(P*2);for(int i=0;i<(1<<l);i+=8){X w0=V7(w,A),w1=V7(w,B),w2=V7(w,C),v=ld(d+i);v=mv(V1(V4(v,V0(M,v),0xaa),V5(v,0xb1)),w2,false);v=mv(V1(V4(v,V0(M,v),0xcc),V5(v,0x4e)),w1,false);v=mv(V1(V4(v,V0(M,v),0xf0),VE(v,v,1)),w0,false);st(d+i,v);if(i+8<(1<<l))w=mv(w,ld(q.wil[__builtin_ctz(~(u32)i>>3)]));}for(int k=3;k+2<=l;k+=2){X z=VD(q.wr[1],q.wr[0],q.wr[0],q.wr[0]);ax<1,1>(k,0,d,z);for(int i=1<<(k+2);i<(1<<l);i+=1<<(k+2))ax<1,0>(k,i,d,z);}if(!(l&1)){int s=1<<(l-1);for(int j=0;j<s;j+=8){X A=sh(h2(ld(d+j))),B=sh(h2(ld(d+s+j)));st(d+j,ad(A,B));st(d+s+j,su(A,B));}}u32 f=sm(pw(1u<<l,P-2),q.r);if(ex)f=sm(f,ex);X F=V6(f);for(int i=0;i<(1<<l);i+=8)st(d+i,mv(ld(d+i),F));}
zt<bool N,class A,class B>PA zs V<u32> conv(zc A&a,zc B&b){int z=1,n=(int)a.size()+(int)b.size()-1;while(z<n)z<<=1;V<u32>x(z),y(z);for(S i=0;i<a.size();i++)x[i]=N?(u32)a[i]:(u32)((u64)a[i]%P);for(S i=0;i<b.size();i++)y[i]=N?(u32)b[i]:(u32)((u64)b[i]%P);int l=__builtin_ctz((u32)z);fw2(l,x.data(),y.data());for(int i=0;i<z;i+=8)st(x.data()+i,mv(ld(x.data()+i),ld(y.data()+i),false));iv(l,x.data(),rr().r);x.resize(n);for(u32&v:x)if(v>=P)v-=P;zr x;}
zt<bool N,class A>PA zs V<u32> square(zc A&a){int z=1,n=(int)a.size()*2-1;while(z<n)z<<=1;V<u32>x(z);for(S i=0;i<a.size();i++)x[i]=N?(u32)a[i]:(u32)((u64)a[i]%P);int l=__builtin_ctz((u32)z);fw(l,x.data());for(int i=0;i<z;i+=8){X X=ld(x.data()+i);st(x.data()+i,mv(X,X,false));}iv(l,x.data(),rr().r);x.resize(n);for(u32&v:x)if(v>=P)v-=P;zr x;}
PA zs void normal_ntt(V<u32>&a,bool I){int l=__builtin_ctz((u32)a.size());if(I)iv(l,a.data());else fw(l,a.data());for(u32&v:a)if(v>=P)v-=P;}
PA zs void invext(zc V<u32>&f,V<u32>&g,S z){S m=g.size(),L=m<<1;V<u32>F(L),Q(L),E(L);for(S i=0;i<std::min(f.size(),L);i++)F[i]=f[i];for(S i=0;i<m;i++)Q[i]=g[i];int l=__builtin_ctz((u32)L);fw2(l,F.data(),Q.data());for(S i=0;i<L;i+=8)st(F.data()+i,mv(ld(F.data()+i),ld(Q.data()+i),false));iv(l,F.data(),rr().r);for(S i=0;i<m;i++)E[i]=F[m+i];fw(l,E.data());for(S i=0;i<L;i+=8)st(E.data()+i,mv(ld(E.data()+i),ld(Q.data()+i),false));iv(l,E.data(),rr().r);g.resize(z);for(S i=m;i<z;i++){u32 x=E[i-m];if(x>=P)x-=P;g[i]=x?P-x:0;}}
PA zs V<V<u32> > cross(zc V<u32>&al,zc V<u32>&ah,zc V<u32>&bl,zc V<u32>&bh,bool hh,int cap=0,int mode=0){int n=(int)al.size()+(int)bl.size()-1,z=1;while(z<n)z<<=1;if(cap)n=z=cap;V<u32>A(z),H(z),B(z),K(z),t(z);for(S i=0;i<al.size();i++)A[i]=al[i]%P,H[i]=ah[i]%P;for(S i=0;i<bl.size();i++)B[i]=bl[i]%P,K[i]=bh[i]%P;int l=__builtin_ctz((u32)z);fw2(l,A.data(),H.data());zs V<u32>cb,ck;if(mode==2)B=cb,K=ck;else{fw2(l,B.data(),K.data());if(mode==1)cb=B,ck=K;}V<V<u32> >r(hh?3:2,V<u32>(n));for(int c=0;c<(hh?3:2);c++){for(int i=0;i<z;i+=8){X x=c==0?mv(ld(A.data()+i),ld(B.data()+i),false):c==1?ad(mv(ld(A.data()+i),ld(K.data()+i)),mv(ld(H.data()+i),ld(B.data()+i))):mv(ld(H.data()+i),ld(K.data()+i),false);st(t.data()+i,x);}iv(l,t.data(),rr().r);for(int i=0;i<n;i++)r[c][i]=t[i]>=P?t[i]-P:t[i];}zr r;}
};
#undef PVL
#undef PVS
#endif
zt<u32 P,u32 G> struct NTT{
zs PI u32 add(u32 a,u32 b){u32 s=a+b;zr s>=P?s-P:s;}zs PI u32 sub(u32 a,u32 b){zr a>=b?a-b:a+P-b;}zs PI u32 mul(u32 a,u32 b){zr(u64)a*b%P;}zs PI u32 normv(u64 a){zr(u32)(a%P);}zs u32 pw(u32 a,u32 e){u32 r=1;for(;e;e>>=1,a=mul(a,a))if(e&1)r=mul(r,a);zr r;}zs bool avx(){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
zs zc bool x=(P<(1u<<30))&&__builtin_cpu_supports("avx2");zr x;
#undef V0
#undef V1
#undef V2
#undef V3
#undef V4
#undef V5
#undef V6
#undef V7
#undef V8
#undef V9
#undef VA
#undef VB
#undef VC
#undef VD
#undef VE
#undef VF
#undef VG
#undef VH
#else
zr false;
#endif
}zs void ntt(V<u32>&a,bool iv){assert((P-1)%a.size()==0);if(a.size()<=1)zr;
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx()&&a.size()>=8){AN<P,G>::normal_ntt(a,iv);zr;}
#endif
int n=(int)a.size();for(int i=1,j=0;i<n;i++){int b=n>>1;for(;j&b;b>>=1)j^=b;j^=b;if(i<j)std::swap(a[i],a[j]);}for(int l=2;l<=n;l<<=1){u32 w=pw(G,(P-1)/l);if(iv)w=pw(w,P-2);for(int i=0;i<n;i+=l){u32 x=1;for(int j=0;j<(l>>1);j++,x=mul(x,w)){u32 u=a[i+j],v=mul(a[i+j+(l>>1)],x);a[i+j]=add(u,v);a[i+j+(l>>1)]=sub(u,v);}}}if(iv){u32 x=pw(n,P-2);for(u32&v:a)v=mul(v,x);}}zs bool invext(zc V<u32>&f,V<u32>&g,S z){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx()&&(g.size()<<1)>=8){AN<P,G>::invext(f,g,z);zr true;}
#endif
zr false;}zt<bool NORMAL,class A,class B> zs V<u32> cv(zc A&a,zc B&b){if(a.empty()||b.empty())zr{};if(std::min(a.size(),b.size())<=56){V<u32>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=(c[i+j]+(u64)(u32)a[i]*(u32)b[j])%P;zr c;}
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::zt conv<NORMAL>(a,b);
#endif
int z=1,need=(int)a.size()+(int)b.size()-1;while(z<need)z<<=1;V<u32>x(z),y(z);for(S i=0;i<a.size();i++)x[i]=NORMAL?(u32)a[i]:(u32)((u64)a[i]%P);for(S i=0;i<b.size();i++)y[i]=NORMAL?(u32)b[i]:(u32)((u64)b[i]%P);ntt(x,0);ntt(y,0);for(int i=0;i<z;i++)x[i]=mul(x[i],y[i]);ntt(x,1);x.resize(need);zr x;}zt<class A,class B> zs V<u32> conv(zc A&a,zc B&b){zr cv<false>(a,b);}zt<class A,class B> zs V<u32> conv_norm(zc A&a,zc B&b){zr cv<true>(a,b);}zt<class A> zs V<u32> square_norm(zc A&a){if(a.empty())zr{};if(a.size()<=56)zr cv<true>(a,a);
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::zt square<true>(a);
#endif
int z=1,need=(int)a.size()*2-1;while(z<need)z<<=1;V<u32>x(z);std::copy(a.begin(),a.end(),x.begin());ntt(x,0);for(int i=0;i<z;i++)x[i]=mul(x[i],x[i]);ntt(x,1);x.resize(need);zr x;}zs V<V<u32> > cross(zc V<u32>&al,zc V<u32>&ah,zc V<u32>&bl,zc V<u32>&bh,bool hh,int cap=0,int mode=0){
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(avx())zr AN<P,G>::cross(al,ah,bl,bh,hh,cap,mode);
#endif
int need=(int)al.size()+(int)bl.size()-1,z=1;while(z<need)z<<=1;if(cap)need=z=cap;V<u32>A(z),H(z),B(z),K(z),t(z);for(S i=0;i<al.size();i++)A[i]=al[i]%P,H[i]=ah[i]%P;for(S i=0;i<bl.size();i++)B[i]=bl[i]%P,K[i]=bh[i]%P;ntt(A,0);ntt(H,0);zs V<u32>cb,ck;if(mode==2)B=cb,K=ck;else{ntt(B,0);ntt(K,0);if(mode==1)cb=B,ck=K;}V<V<u32> >r(hh?3:2,V<u32>(need));for(int c=0;c<(hh?3:2);c++){for(int i=0;i<z;i++)t[i]=c==0?mul(A[i],B[i]):c==1?add(mul(A[i],K[i]),mul(H[i],B[i])):mul(H[i],K[i]);ntt(t,1);std::copy(t.begin(),t.begin()+need,r[c].begin());}zr r;}};using N1=NTT<998244353,3>;using N2=NTT<754974721,11>;using N3=NTT<469762049,3>;using N4=NTT<167772161,3>;using N5=NTT<1224736769,3>;zs zc u64 P1=998244353ULL,P2=754974721ULL,P3=469762049ULL;PI u128 crt3(u32 a,u32 b,u32 c){zs zc u64 i12=I64(P1%P2,P2),i123=I64((u128)P1*P2%P3,P3);u64 t2=(u64)((b+P2-a%P2)%P2)*i12%P2,x=(u64)a+P1*t2,t3=(u64)((c+P3-x%P3)%P3)*i123%P3;zr(u128)x+(u128)P1*P2*t3;}zt<u64 M> PI u32 crt3m(u32 a,u32 b,u32 c){zs zc u64 i12=I64(P1%P2,P2),i123=I64((u128)P1*P2%P3,P3),q1=P1%M,q12=q1*(P2%M)%M;u64 t2=(u64)((b+P2-a%P2)%P2)*i12%P2,x=(u64)a+P1*t2,t3=(u64)((c+P3-x%P3)%P3)*i123%P3,r=a%M;r=(r+q1*(t2%M)%M)%M;r=(r+q12*(t3%M)%M)%M;zr(u32)r;}zt<u64 MOD> struct DN{enum{yes=0};};zt<>struct DN<998244353ULL>{enum{yes=1};zd N1 N;};zt<>struct DN<754974721ULL>{enum{yes=1};zd N2 N;};zt<>struct DN<469762049ULL>{enum{yes=1};zd N3 N;};zt<>struct DN<167772161ULL>{enum{yes=1};zd N4 N;};zt<>struct DN<1224736769ULL>{enum{yes=1};zd N5 N;};zt<u64 MOD,bool DIRECT=DN<MOD>::yes> struct Conv;zt<u64 MOD>struct Conv<MOD,true>{zd zy CT<MOD>::type T;zs V<T>go(zc V<T>&a,zc V<T>&b){zd zy DN<MOD>::N N;zr N::conv_norm(a,b);}zs V<T>sq(zc V<T>&a){zd zy DN<MOD>::N N;zr N::square_norm(a);}};zt<u64 MOD>struct Conv<MOD,false>{zd zy CT<MOD>::type T;zs V<T>naive(zc V<T>&a,zc V<T>&b){V<T>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=MO<MOD>::add(c[i+j],MO<MOD>::mul(a[i],b[j]));zr c;}zs V<T>go32(zc V<T>&a,zc V<T>&b){auto x=N1::conv(a,b),y=N2::conv(a,b),z=N3::conv(a,b);V<T>c(x.size());for(S i=0;i<c.size();i++)c[i]=(T)crt3m<MOD>(x[i],y[i],z[i]);zr c;}zs V<T>go64(zc V<T>&a,zc V<T>&b){V<u32>al(a.size()),ah(a.size()),bl(b.size()),bh(b.size());for(S i=0;i<a.size();i++)al[i]=(u32)a[i],ah[i]=(u32)((u64)a[i]>>32);for(S i=0;i<b.size();i++)bl[i]=(u32)b[i],bh[i]=(u32)((u64)b[i]>>32);bool h=MOD!=0;auto r1=N1::cross(al,ah,bl,bh,h),r2=N2::cross(al,ah,bl,bh,h),r3=N3::cross(al,ah,bl,bh,h);V<T>c(r1[0].size());if(MOD==0){for(S i=0;i<c.size();i++){u64 lo=(u64)crt3(r1[0][i],r2[0][i],r3[0][i]),cr=(u64)crt3(r1[1][i],r2[1][i],r3[1][i]);c[i]=(T)(lo+(cr<<32));}}else{u64 r64=(u64)((u128(1)<<64)%MOD);for(S i=0;i<c.size();i++){u64 lo=(u64)(crt3(r1[0][i],r2[0][i],r3[0][i])%MOD),cr=(u64)(crt3(r1[1][i],r2[1][i],r3[1][i])%MOD),hi=(u64)(crt3(r1[2][i],r2[2][i],r3[2][i])%MOD),x=(u64)(((u128)lo+((u128)cr<<32))%MOD);c[i]=(T)MO<MOD>::add((T)x,(T)M64(hi,r64,MOD));}}zr c;}zs V<T>go(zc V<T>&a,zc V<T>&b){if(a.empty()||b.empty())zr{};if(std::min(a.size(),b.size())<=24)zr naive(a,b);zr go_dispatch(a,b,std::integral_constant<bool,(MOD!=0&&MOD<=0xffffffffULL)>());}zs V<T>sq(zc V<T>&a){zr go(a,a);}zs V<T>go_dispatch(zc V<T>&a,zc V<T>&b,std::true_type){zr go32(a,b);}zs V<T>go_dispatch(zc V<T>&a,zc V<T>&b,std::false_type){zr go64(a,b);}};}zt<u64 MOD> struct Poly{
zd zy pd::CT<MOD>::type T;zd pd::MO<MOD> O;V<T>a;Poly(){}Poly(S n):a(n){}Poly(zc V<T>&v):a(v){norm();}zt<class U> Poly(zc V<U>&v){a.resize(v.size());for(S i=0;i<v.size();i++)a[i]=O::norm(v[i]);norm();}zt<class U> Poly(std::initializer_list<U> v){a.reserve(v.size());for(auto x:v)a.push_back(O::norm(x));norm();}S size()zc{zr a.size();}bool empty()zc{zr a.empty();}int deg()zc{zr(int)a.size()-1;}T operator[](S i)zc{zr i<a.size()?a[i]:0;}T& operator[](S i){zr a[i];}zs T inv_int(S x){zr inv_int_dispatch(x,std::integral_constant<bool,pd::DN<MOD>::yes>());}zs T inv_int_dispatch(S x,std::false_type){zr O::inv(O::norm((u64)x));}zs T inv_int_dispatch(S x,std::true_type){assert(x&&x<MOD);zs V<T>v(2,1);v[0]=0;if(v.size()<=x){S o=v.size();v.resize(x+1);for(S i=o;i<=x;i++)v[i]=(T)(MOD-(u64)(MOD/i)*v[MOD%i]%MOD);}zr v[x];}void norm(){while(!a.empty()&&a.back()==0)a.pop_back();}Poly pre(S n)zc{if(a.size()<=n)zr *this;Poly r=*this;r.a.resize(n);r.norm();zr r;}Poly& cut(S n){if(a.size()>n)a.resize(n);norm();zr *this;}Poly rev(S n=0)zc{Poly r=*this;if(n)r.a.resize(n);std::reverse(r.a.begin(),r.a.end());r.norm();zr r;}zf Poly operator+(Poly x,zc Poly&y){zr x+=y;}zf Poly operator-(Poly x,zc Poly&y){zr x-=y;}zf Poly operator*(zc Poly&x,zc Poly&y){Poly r;r.a=(&x==&y)?pd::Conv<MOD>::sq(x.a):pd::Conv<MOD>::go(x.a,y.a);r.norm();zr r;}Poly sqr()zc{Poly r;r.a=pd::Conv<MOD>::sq(a);r.norm();zr r;}zf bool operator==(zc Poly&x,zc Poly&y){zr x.a==y.a;}zf bool operator!=(zc Poly&x,zc Poly&y){zr !(x==y);}Poly& operator+=(zc Poly&b){if(a.size()<b.size())a.resize(b.size());for(S i=0;i<b.size();i++)a[i]=O::add(a[i],b.a[i]);norm();zr *this;}Poly& operator-=(zc Poly&b){if(a.size()<b.size())a.resize(b.size());for(S i=0;i<b.size();i++)a[i]=O::sub(a[i],b.a[i]);norm();zr *this;}Poly& operator*=(zc Poly&b){zr *this=*this*b;}Poly operator-()zc{Poly r=*this;for(T&x:r.a)x=O::neg(x);zr r;}Poly& operator+=(T k){if(a.empty())a.resize(1);a[0]=O::add(a[0],k);norm();zr *this;}Poly& operator-=(T k){if(a.empty())a.resize(1);a[0]=O::sub(a[0],k);norm();zr *this;}Poly& operator*=(T k){for(T&x:a)x=O::mul(x,k);norm();zr *this;}Poly& operator/=(T k){zr *this*=O::inv(k);}zf Poly operator+(Poly x,T k){zr x+=k;}zf Poly operator+(T k,Poly x){zr x+=k;}zf Poly operator-(Poly x,T k){zr x-=k;}zf Poly operator-(T k,zc Poly&x){zr(-x)+k;}zf Poly operator*(Poly x,T k){zr x*=k;}zf Poly operator*(T k,Poly x){zr x*=k;}zf Poly operator/(Poly x,T k){zr x/=k;}Poly shl(S k)zc{if(empty())zr{};Poly r;r.a.assign(k,0);r.a.insert(r.a.end(),a.begin(),a.end());zr r;}Poly shr(S k)zc{if(k>=a.size())zr{};zr Poly(V<T>(a.begin()+k,a.end()));}zf Poly operator<<(zc Poly&x,S k){zr x.shl(k);}zf Poly operator>>(zc Poly&x,S k){zr x.shr(k);}Poly deriv()zc{if(a.size()<2)zr{};Poly r(a.size()-1);for(S i=1;i<a.size();i++)r.a[i-1]=O::mul(a[i],O::norm((u64)i));r.norm();zr r;}Poly integr()zc{Poly r(a.size()+1);for(S i=0;i<a.size();i++)r.a[i+1]=O::mul(a[i],inv_int(i+1));r.norm();zr r;}T eval(T x)zc{T r=0;for(S i=a.size();i--;)r=O::add(O::mul(r,x),a[i]);zr r;}T operator()(T x)zc{zr eval(x);}Poly inv(S n=0)zc{if(!n)n=a.size();assert(n&&!a.empty());zr inv_dispatch(n,std::integral_constant<bool,pd::DN<MOD>::yes>());}Poly inv_dispatch(S n,std::false_type)zc{Poly g{O::inv(a[0])};S m=1;while(m<n){S z=std::min(n,m<<1);Poly f=pre(z),t=(f*g).pre(z);t.a.resize(z);for(S i=0;i<z;i++)t.a[i]=O::neg(t.a[i]);t.a[0]=O::add(t.a[0],O::norm(2));g=(g*t).pre(z);m=z;}g.a.resize(n);g.norm();zr g;}Poly inv_dispatch(S n,std::true_type)zc{zd zy pd::DN<MOD>::N NN;Poly g{O::inv(a[0])};S m=1;while(m<n){S L=m<<1,z=std::min(n,L);if(NN::invext(a,g.a,z)){m=L;continue;}V<u32>f(L),gh(L),e(L);for(S i=0;i<std::min(a.size(),L);i++)f[i]=(u32)a[i];for(S i=0;i<m;i++)gh[i]=(u32)g.a[i];NN::ntt(f,0);NN::ntt(gh,0);for(S i=0;i<L;i++)f[i]=NN::mul(f[i],gh[i]);NN::ntt(f,1);for(S i=0;i<m;i++)e[i]=f[m+i];NN::ntt(e,0);for(S i=0;i<L;i++)e[i]=NN::mul(e[i],gh[i]);NN::ntt(e,1);g.a.resize(z);for(S i=m;i<z;i++)g.a[i]=O::neg((T)e[i-m]);m=L;}g.a.resize(n);g.norm();zr g;}Poly div(zc Poly&b,S n=0)zc{if(!n)n=a.size();zr(*this*b.inv(n)).pre(n);}Poly log(S n=0)zc{if(!n)n=a.size();assert(!a.empty()&&a[0]==O::norm(1));Poly r=(deriv()*inv(n)).pre(n-1).integr();r.a.resize(n);r.norm();zr r;}Poly exp(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);zr exp_dispatch(n,std::integral_constant<bool,pd::DN<MOD>::yes>());}Poly exp_dispatch(S n,std::false_type)zc{Poly g{1};S m=1;while(m<n){S z=std::min(n,m<<1);Poly q=pre(z)-g.log(z);q.a.resize(z);q.a[0]=O::add(q.a[0],O::norm(1));g=(g*q).pre(z);m=z;}g.a.resize(n);g.norm();zr g;}
Poly exp_dispatch(S n,std::true_type)zc{zd zy pd::DN<MOD>::N NN;Poly g{1};S m=1;while(m<n){S L=m<<1,z=std::min(n,L);Poly h=g.inv(L);V<u32>d(L),iv(L);for(S i=1;i<g.size();i++)d[i-1]=NN::mul((u32)g.a[i],(u32)(i%MOD));for(S i=0;i<h.size();i++)iv[i]=(u32)h.a[i];NN::ntt(d,0);NN::ntt(iv,0);for(S i=0;i<L;i++)d[i]=NN::mul(d[i],iv[i]);NN::ntt(d,1);V<u32>G(L),E(L);for(S i=0;i<g.size();i++)G[i]=(u32)g.a[i];for(S j=0;j<m&&m+j<z;j++){S k=m+j;u32 lg=NN::mul(d[k-1],(u32)inv_int(k));E[j]=NN::sub((u32)(k<a.size()?a[k]:0),lg);}NN::ntt(G,0);NN::ntt(E,0);for(S i=0;i<L;i++)G[i]=NN::mul(G[i],E[i]);NN::ntt(G,1);g.a.resize(z);for(S j=0;j<m&&m+j<z;j++)g.a[m+j]=(T)G[j];m=L;}g.a.resize(n);g.norm();zr g;}
zs T mod_sqrt(T n){
if(MOD==2)zr n;assert(MOD&&(MOD&1));if(!n)zr 0;if(O::pw(n,(MOD-1)>>1)!=1)zr 0;
if((MOD&3)==3)zr O::pw(n,(MOD+1)>>2);u64 q=MOD-1,s=0;while(!(q&1))q>>=1,++s;T z=2;while(O::pw(z,(MOD-1)>>1)!=MOD-1)z=O::add(z,1);
T c=O::pw(z,q),x=O::pw(n,(q+1)>>1),t=O::pw(n,q);u64 m=s;while(t!=1){u64 i=1;T tt=O::mul(t,t);while(i<m&&tt!=1)tt=O::mul(tt,tt),++i;T b=O::pw(c,u64(1)<<(m-i-1));x=O::mul(x,b);c=O::mul(b,b);t=O::mul(t,c);m=i;}zr x;
}
Poly sqrt(S n=0)zc{
if(!n)n=a.size();assert(MOD!=0);if(empty())zr{};S p=0;while(p<a.size()&&!a[p])++p;if(p){assert(!(p&1));Poly r=shr(p).sqrt(n-p/2);zr r.shl(p/2).pre(n);}T s=mod_sqrt(a[0]);assert(s);Poly g{s};T inv2=O::inv(O::norm(2));S m=1;
while(m<n){S z=std::min(n,m<<1);g=(g+(pre(z)*g.inv(z)).pre(z))*inv2;g.cut(z);m=z;}g.a.resize(n);g.norm();zr g;
}
Poly pow_scalar(T k,S n=0)zc{if(!n)n=a.size();assert(!empty()&&a[0]==O::norm(1));zr(log(n)*k).exp(n);}
Poly pow(u64 k,S n=0)zc{
if(!n)n=a.size();if(!n)zr{};if(k==0)zr Poly{O::norm(1)};
S p=0;while(p<a.size()&&!a[p])++p;if(p==a.size()||p>(n-1)/k)zr{};S sh=p*k;if(sh>=n)zr{};
T c=a[p],ic=O::inv(c);Poly f=shr(p)*ic;S need=n-sh;Poly r=(f.log(need)*O::norm(k)).exp(need);r*=O::pw(c,k);r=r.shl(sh);r.a.resize(n);r.norm();zr r;
}
Q<Poly,Poly> divmod(zc Poly&b)zc{
assert(!b.empty());if(a.size()<b.size())zr{{},*this};S n=a.size()-b.size()+1;Poly q=(rev().pre(n)*b.rev().inv(n)).pre(n).rev(n);Poly r=*this-q*b;r.cut(b.size()-1);zr{q,r};
}
zf Poly operator/(zc Poly&x,zc Poly&y){zr x.divmod(y).first;}zf Poly operator%(zc Poly&x,zc Poly&y){zr x.divmod(y).second;}Poly& operator/=(zc Poly&b){zr *this=*this/b;}Poly& operator%=(zc Poly&b){zr *this=*this%b;}
Poly compose(zc Poly&g,S n=0)zc{
if(!n)n=a.size();if(!n||empty())zr{};assert(g.empty()||g[0]==0);S m=1;while(m*m<n)++m;V<Poly>pw(m);pw[0]=Poly{O::norm(1)};for(S i=1;i<m;i++)pw[i]=(pw[i-1]*g).pre(n);Poly gm=(pw[m-1]*g).pre(n),res;S blocks=(std::min(a.size(),n)+m-1)/m;
for(S bb=blocks;bb--;){if(!res.empty())res=(res*gm).pre(n);Poly cur;cur.a.resize(n);S base=bb*m;for(S i=0;i<m&&base+i<a.size()&&base+i<n;i++){T c=a[base+i];if(!c)continue;for(S j=0;j<pw[i].size()&&j<n;j++)cur.a[j]=O::add(cur.a[j],O::mul(c,pw[i].a[j]));}cur.norm();res+=cur;res.cut(n);}zr res;
}
Poly revert(S n=0)zc{
if(!n)n=a.size();assert(n&&a.size()>1&&a[0]==0);if(n==1)zr{};Poly g(2);g.a[1]=O::inv(a[1]);S m=2;while(m<n){S z=std::min(n,m<<1);Poly e=compose(g,z);if(e.a.size()<2)e.a.resize(2);e.a[1]=O::sub(e.a[1],O::norm(1));e.norm();Poly d=deriv().compose(g,z);g=(g-e.div(d,z)).pre(z);m=z;}g.a.resize(n);g.norm();zr g;
}
Q<Poly,Poly> sincos(S n=0)zc{
if(!n)n=a.size();assert(MOD&&(empty()||a[0]==0));T I=mod_sqrt(O::neg(O::norm(1)));assert(I);Poly e=(*this*I).exp(n),ie=e.inv(n);T h=O::inv(O::norm(2)),hi=O::inv(O::mul(O::norm(2),I));zr{(e-ie)*hi,(e+ie)*h};
}
Poly sin(S n=0)zc{zr sincos(n).first;}Poly cos(S n=0)zc{zr sincos(n).second;}
Poly tan(S n=0)zc{if(!n)n=a.size();auto sc=sincos(n);zr sc.first.div(sc.second,n);}
Poly asin(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);Poly q=-pre(n).sqr().pre(n);q+=O::norm(1);zr(deriv()*q.sqrt(n).inv(n)).pre(n-1).integr().pre(n);}
Poly atan(S n=0)zc{if(!n)n=a.size();assert(empty()||a[0]==0);Poly q=pre(n).sqr().pre(n);q+=O::norm(1);zr(deriv()*q.inv(n)).pre(n-1).integr().pre(n);}
Poly acos(T c0,S n=0)zc{if(!n)n=a.size();Poly r=-asin(n);r+=c0;zr r;}
V<T> chirpz(T z,S m)zc{
V<T>out(m);S n=a.size();if(!m||!n)zr out;if(!z){out[0]=eval(O::norm(1));for(S k=1;k<m;k++)out[k]=a[0];zr out;}T iz=O::inv(z);Poly A(n),B(n+m-1);T cur=1,q=1;for(S i=0;i<n;i++){A.a[i]=O::mul(a[i],cur);cur=O::mul(cur,q);q=O::mul(q,z);}S off=n-1;B.a[off]=1;cur=1;q=1;for(S t=1;t<n;t++){cur=O::mul(cur,q);B.a[off-t]=cur;q=O::mul(q,iz);}cur=1;q=iz;for(S j=1;j<m;j++){cur=O::mul(cur,q);B.a[off+j]=cur;q=O::mul(q,iz);}Poly C=A*B;cur=1;q=z;for(S k=0;k<m;k++){out[k]=O::mul(C[off+k],cur);cur=O::mul(cur,q);q=O::mul(q,z);}zr out;
}
Poly shift(T c)zc{
S n=a.size();if(!n)zr{};V<T> fac(n),ifac(n);fac[0]=1;for(S i=1;i<n;i++)fac[i]=O::mul(fac[i-1],O::norm((u64)i));ifac[n-1]=O::inv(fac[n-1]);for(S i=n-1;i;i--)ifac[i-1]=O::mul(ifac[i],O::norm((u64)i));
Poly A(n),B(n);for(S i=0;i<n;i++)A.a[n-1-i]=O::mul(a[i],fac[i]);T pw=1;for(S i=0;i<n;i++){B.a[i]=O::mul(pw,ifac[i]);pw=O::mul(pw,c);}Poly C=A*B,R(n);for(S i=0;i<n;i++)R.a[i]=O::mul(C[n-1-i],ifac[i]);R.norm();zr R;
}
V<T> multipoint(zc V<T>&xs)zc{
S n=xs.size();if(!n)zr{};S z=1;while(z<n)z<<=1;V<Poly>tr(z<<1);for(S i=0;i<z;i++)tr[z+i]=i<n?Poly{O::neg(xs[i]),O::norm(1)}:Poly{O::norm(1)};for(S i=z;i-- >1;)tr[i]=tr[i<<1]*tr[i<<1|1];V<Poly>rem(z<<1);rem[1]=*this%tr[1];for(S i=1;i<z;i++){rem[i<<1]=rem[i]%tr[i<<1];rem[i<<1|1]=rem[i]%tr[i<<1|1];}V<T>r(n);for(S i=0;i<n;i++)r[i]=rem[z+i].empty()?0:rem[z+i].a[0];zr r;
}
zs Poly interpolate(zc V<T>&xs,zc V<T>&ys){
S n=xs.size();assert(n==ys.size());if(!n)zr{};S z=1;while(z<n)z<<=1;V<Poly>tr(z<<1);for(S i=0;i<z;i++)tr[z+i]=i<n?Poly{O::neg(xs[i]),O::norm(1)}:Poly{O::norm(1)};for(S i=z;i-- >1;)tr[i]=tr[i<<1]*tr[i<<1|1];V<T>d=tr[1].deriv().multipoint(xs);V<Poly>v(z<<1);for(S i=0;i<n;i++)v[z+i]=Poly{O::mul(ys[i],O::inv(d[i]))};for(S i=n;i<z;i++)v[z+i]={};for(S i=z;i-- >1;)v[i]=v[i<<1]*tr[i<<1|1]+v[i<<1|1]*tr[i<<1];zr v[1].pre(n);
}
};
zt<u64 MOD> V<zy Poly<MOD>::T> berlekamp_massey(zc V<zy Poly<MOD>::T>&s){
zd Poly<MOD> P;zd zy P::T T;zd zy P::O O;V<T>C(1,1),B(1,1);int L=0,m=1;T b=1;
for(S n=0;n<s.size();n++){T d=s[n];for(int i=1;i<=L;i++)d=O::add(d,O::mul(C[i],s[n-i]));if(!d){++m;continue;}T coef=O::mul(d,O::inv(b));V<T>Tc=C;if(C.size()<B.size()+m)C.resize(B.size()+m);for(S j=0;j<B.size();j++)C[j+m]=O::sub(C[j+m],O::mul(coef,B[j]));if(2*L<=(int)n){L=(int)n+1-L;B=Tc;b=d;m=1;}else ++m;}C.erase(C.begin());for(T&x:C)x=O::neg(x);zr C;
}
zt<u64 MOD> zy Poly<MOD>::T bostan_mori(Poly<MOD> p,Poly<MOD> q,u64 k){
zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;assert(!q.empty()&&q.a[0]);
while(k){P qm=q;for(S i=1;i<qm.size();i+=2)qm.a[i]=O::neg(qm.a[i]);P s=p*qm,t=q*qm;V<T>np,nq;np.reserve((s.size()+1)/2);nq.reserve((t.size()+1)/2);for(S i=k&1;i<s.size();i+=2)np.push_back(s.a[i]);for(S i=0;i<t.size();i+=2)nq.push_back(t.a[i]);p=P(np);q=P(nq);k>>=1;}zr O::mul(p.empty()?0:p.a[0],O::inv(q.a[0]));
}
zt<u64 MOD> Poly<MOD> poly_gcd(Poly<MOD>a,Poly<MOD>b){zd zy Poly<MOD>::O O;while(!b.empty()){a%=b;std::swap(a,b);}if(!a.empty())a/=a.a.back();zr a;}
zt<u64 MOD> std::tuple<Poly<MOD>,Poly<MOD>,Poly<MOD> > poly_exgcd(Poly<MOD>a,Poly<MOD>b){zd Poly<MOD>P;P x0{1},x1,y0,y1{1};while(!b.empty()){auto qr=a.divmod(b);P nx=x0-qr.first*x1,ny=y0-qr.first*y1;a=b;b=qr.second;x0=x1;x1=nx;y0=y1;y1=ny;}if(!a.empty()){auto c=P::O::inv(a.a.back());a*=c;x0*=c;y0*=c;}zr std::make_tuple(a,x0,y0);}
zt<u64 MOD> zy Poly<MOD>::T resultant(Poly<MOD>a,Poly<MOD>b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;if(a.empty()||b.empty())zr 0;T ans=1;if(a.deg()<b.deg()){if((a.deg()*b.deg())&1)ans=O::neg(ans);std::swap(a,b);}for(;;){if(b.deg()==0)zr O::mul(ans,O::pw(b.a[0],a.deg()));P r=a%b;if(r.empty())zr 0;if((a.deg()*b.deg())&1)ans=O::neg(ans);ans=O::mul(ans,O::pw(b.a.back(),(u64)(a.deg()-r.deg())));a=b;b=r;}}
zt<u64 MOD> zy Poly<MOD>::T linear_nth(zc V<zy Poly<MOD>::T>&init,zc V<zy Poly<MOD>::T>&rec,u64 k){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;if(k<init.size())zr init[(S)k];S d=rec.size();assert(init.size()>=d&&d);P q(d+1);q.a[0]=1;for(S i=0;i<d;i++)q.a[i+1]=O::neg(rec[i]);P p=(P(V<T>(init.begin(),init.begin()+d))*q).pre(d);zr bostan_mori(p,q,k);}
zt<u64 MOD> void fwt_or(V<zy Poly<MOD>::T>&a,bool inv=false){zd zy Poly<MOD>::O O;for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++)a[i+j+l]=inv?O::sub(a[i+j+l],a[i+j]):O::add(a[i+j+l],a[i+j]);}
zt<u64 MOD> void fwt_and(V<zy Poly<MOD>::T>&a,bool inv=false){zd zy Poly<MOD>::O O;for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++)a[i+j]=inv?O::sub(a[i+j],a[i+j+l]):O::add(a[i+j],a[i+j+l]);}
zt<u64 MOD> void fwt_xor(V<zy Poly<MOD>::T>&a,bool inv=false){zd Poly<MOD>P;zd zy P::O O;zy P::T h=inv?O::inv(O::norm(2)):O::norm(1);for(S l=1;l<a.size();l<<=1)for(S i=0;i<a.size();i+=l<<1)for(S j=0;j<l;j++){auto x=a[i+j],y=a[i+j+l];a[i+j]=O::mul(O::add(x,y),h);a[i+j+l]=O::mul(O::sub(x,y),h);}}
zt<u64 MOD,int TYPE> V<zy Poly<MOD>::T> bitwise_convolution(V<zy Poly<MOD>::T>a,V<zy Poly<MOD>::T>b){assert(a.size()==b.size()&&!a.empty()&&!(a.size()&(a.size()-1)));if(TYPE==0)fwt_or<MOD>(a),fwt_or<MOD>(b);else if(TYPE==1)fwt_and<MOD>(a),fwt_and<MOD>(b);else fwt_xor<MOD>(a),fwt_xor<MOD>(b);for(S i=0;i<a.size();i++)a[i]=Poly<MOD>::O::mul(a[i],b[i]);if(TYPE==0)fwt_or<MOD>(a,1);else if(TYPE==1)fwt_and<MOD>(a,1);else fwt_xor<MOD>(a,1);zr a;}
zt<u64 MOD> zy Poly<MOD>::T lagrange_consecutive(zc V<zy Poly<MOD>::T>&y,zy Poly<MOD>::T x){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S n=y.size();if(!n)zr 0;V<T>pre(n+1),suf(n+1),fac(n),ifac(n);pre[0]=suf[n]=fac[0]=1;for(S i=0;i<n;i++)pre[i+1]=O::mul(pre[i],O::sub(x,O::norm((u64)i)));for(S i=n;i--;)suf[i]=O::mul(suf[i+1],O::sub(x,O::norm((u64)i)));for(S i=1;i<n;i++)fac[i]=O::mul(fac[i-1],O::norm((u64)i));ifac[n-1]=O::inv(fac[n-1]);for(S i=n-1;i;i--)ifac[i-1]=O::mul(ifac[i],O::norm((u64)i));T ans=0;for(S i=0;i<n;i++){T v=O::mul(y[i],O::mul(pre[i],suf[i+1]));v=O::mul(v,O::mul(ifac[i],ifac[n-1-i]));if((n-1-i)&1)v=O::neg(v);ans=O::add(ans,v);}zr ans;}
zt<u64 MOD> V<zy Poly<MOD>::T> subset_convolution(zc V<zy Poly<MOD>::T>&a,zc V<zy Poly<MOD>::T>&b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S N=a.size();assert(N==b.size()&&N&&!(N&(N-1)));int k=__builtin_ctzll(N);V<T>A((k+1)*N),B((k+1)*N),C((k+1)*N);for(S s=0;s<N;s++){int r=__builtin_popcountll(s);A[(S)r*N+s]=a[s];B[(S)r*N+s]=b[s];}for(int r=0;r<=k;r++)for(int bit=0;bit<k;bit++)for(S s=0;s<N;s++)if(s&(S(1)<<bit)){A[(S)r*N+s]=O::add(A[(S)r*N+s],A[(S)r*N+(s^(S(1)<<bit))]);B[(S)r*N+s]=O::add(B[(S)r*N+s],B[(S)r*N+(s^(S(1)<<bit))]);}for(S s=0;s<N;s++)for(int r=0;r<=k;r++)for(int i=0;i<=r;i++)C[(S)r*N+s]=O::add(C[(S)r*N+s],O::mul(A[(S)i*N+s],B[(S)(r-i)*N+s]));for(int r=0;r<=k;r++)for(int bit=0;bit<k;bit++)for(S s=0;s<N;s++)if(s&(S(1)<<bit))C[(S)r*N+s]=O::sub(C[(S)r*N+s],C[(S)r*N+(s^(S(1)<<bit))]);V<T>res(N);for(S s=0;s<N;s++)res[s]=C[(S)__builtin_popcountll(s)*N+s];zr res;}
zt<u64 MOD> V<zy Poly<MOD>::T> dirichlet_convolution(zc V<zy Poly<MOD>::T>&a,zc V<zy Poly<MOD>::T>&b){zd Poly<MOD>P;zd zy P::T T;zd zy P::O O;S n=std::min(a.size(),b.size());V<T>c(n);for(S i=1;i<n;i++)for(S j=1;i*j<n;j++)c[i*j]=O::add(c[i*j],O::mul(a[i],b[j]));zr c;}
inline V<u32> convolution_mod(zc V<u32>&a,zc V<u32>&b,u32 M){
if(a.empty()||b.empty())zr{};if(M==1)zr V<u32>(a.size()+b.size()-1);if(M==998244353u)zr pd::N1::conv(a,b);if(M==754974721u)zr pd::N2::conv(a,b);if(M==469762049u)zr pd::N3::conv(a,b);if(M==167772161u)zr pd::N4::conv(a,b);if(M==1224736769u)zr pd::N5::conv(a,b);if(std::min(a.size(),b.size())<=24){V<u32>c(a.size()+b.size()-1);for(S i=0;i<a.size();i++)for(S j=0;j<b.size();j++)c[i+j]=(c[i+j]+(u64)(a[i]%M)*(b[j]%M))%M;zr c;}auto x=pd::N1::conv(a,b),y=pd::N2::conv(a,b),z=pd::N3::conv(a,b);V<u32>c(x.size());zs zc u64 i12=pd::I64(pd::P1%pd::P2,pd::P2),i123=pd::I64((u128)pd::P1*pd::P2%pd::P3,pd::P3);u64 q1=pd::P1%M,q12=q1*(pd::P2%M)%M;for(S i=0;i<c.size();i++){u64 t2=(u64)((y[i]+pd::P2-x[i]%pd::P2)%pd::P2)*i12%pd::P2,X=(u64)x[i]+pd::P1*t2,t3=(u64)((z[i]+pd::P3-X%pd::P3)%pd::P3)*i123%pd::P3,r=x[i]%M;r=(r+q1*(t2%M))%M;r=(r+q12*(t3%M))%M;c[i]=(u32)r;}zr c;
}
#undef zr
#undef zs
#undef zc
#undef zt
#undef zy
#undef zd
#undef zf
#endif
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define fst first
#define sed second
#define pref static inline
using namespace std;using hint=__int128;using uhint=unsigned __int128;
using us=unsigned short;using ui=unsigned int;using ll=long long;using ull=unsigned long long;
using db=double;using ldb=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;
using pil=pair<int,ll>;using pli=pair<ll,int>;using vi=vector<int>;using vl=vector<ll>;
using vpi=vector<pii>;using vpl=vector<pll>;using vpil=vector<pil>;using vpli=vector<pli>;
ostream& out128(ostream&,uhint,bool);ostream& operator<<(ostream&,hint);ostream& operator<<(ostream&,uhint);
namespace mystl{
const int SI=1<<22,SO=1<<20;pref size_t fr(void*p,size_t n){
#ifdef __linux__
return fread_unlocked(p,1,n,stdin);
#else
return fread(p,1,n,stdin);
#endif
}
unsigned char mp[1<<16];struct Init{Init(){memset(mp,255,sizeof mp);for(unsigned i=0;i<10;++i)for(unsigned j=0;j<10;++j){unsigned char s[2]={static_cast<unsigned char>('0'+i),static_cast<unsigned char>('0'+j)};uint16_t x;memcpy(&x,s,2);mp[x]=static_cast<unsigned char>(i*10+j);}}}init;
pref unsigned pv(const char*p){uint16_t x;memcpy(&x,p,2);return mp[x];}
struct IB:streambuf{
char b[SI];bool eofed=false;IB(){setg(b,b,b);}
int_type underflow()override{if(gptr()<egptr())return traits_type::to_int_type(*gptr());size_t n=fr(b,SI);if(!n)return traits_type::eof();setg(b,b,b+n);return traits_type::to_int_type(*gptr());}
inline void commit(char*p){gbump(static_cast<int>(p-gptr()));}
inline bool refill(char*&p,char*&e){commit(p);if(traits_type::eq_int_type(underflow(),traits_type::eof())){eofed=true;return false;}p=gptr();e=egptr();return true;}
inline bool head(char*&p,char*&e,bool&neg){eofed=false;for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}neg=false;if(*p=='-'||*p=='+'){neg=*p=='-';++p;if(p==e&&!refill(p,e))return false;}return true;}
template<class T,class U>inline bool slow(T&x,bool neg,char*&p,char*&e){U y=0;bool ok=false;for(;;){while(p<e){unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c>9){commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}ok=true;y=static_cast<U>(y*10+c);++p;}if(!refill(p,e)){if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}}}
template<class T,class U,int K>inline bool num(T&x){x=0;char*p=gptr(),*e=egptr();bool neg;if(!head(p,e,neg))return false;if(e-p<2*K+1)return slow<T,U>(x,neg,p,e);U y=0;bool ok=false;for(int i=0;i<K;++i){unsigned v=pv(p);if(v>=255)break;ok=true;y=static_cast<U>(y*100+static_cast<U>(v));p+=2;}unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c<=9){ok=true;y=static_cast<U>(y*10+c);++p;}commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}
inline bool read(short&x){return num<short,unsigned short,5>(x);}inline bool read(us&x){return num<us,us,5>(x);}inline bool read(int&x){return num<int,unsigned,5>(x);}inline bool read(unsigned&x){return num<unsigned,unsigned,5>(x);}inline bool read(long&x){return sizeof(long)<=4?num<long,unsigned long,5>(x):num<long,unsigned long,10>(x);}inline bool read(unsigned long&x){return sizeof(unsigned long)<=4?num<unsigned long,unsigned long,5>(x):num<unsigned long,unsigned long,10>(x);}inline bool read(ll&x){return num<ll,ull,10>(x);}inline bool read(ull&x){return num<ull,ull,10>(x);}inline bool read(hint&x){return num<hint,uhint,20>(x);}inline bool read(uhint&x){return num<uhint,uhint,20>(x);}
inline bool read(char&x){x=0;eofed=false;char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e){x=*p++;commit(p);return true;}if(!refill(p,e))return false;}}
inline bool read(string&x){eofed=false;x.clear();char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}for(;;){char*q=p;while(q<e&&static_cast<unsigned char>(*q)>32)++q;x.append(p,static_cast<size_t>(q-p));p=q;if(p<e){commit(p);return true;}if(!refill(p,e))return true;}}
template<class T>inline bool fp(T&x){x=0;string s;if(!read(s))return false;return cv(s.c_str(),x);}static inline bool cv(const char*s,float&x){char*e=nullptr;x=strtof(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,double&x){char*e=nullptr;x=strtod(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,long double&x){char*e=nullptr;x=strtold(s,&e);return e!=s&&*e==0;}
}ib;
struct OB:streambuf{
char b[SO];OB(){setp(b,b+SO);}~OB(){sync();}
int sync()override{size_t n=static_cast<size_t>(pptr()-pbase());if(n&&fwrite(b,1,n,stdout)!=n)return -1;setp(b,b+SO);return 0;}
int_type overflow(int_type c=traits_type::eof())override{if(sync())return traits_type::eof();if(!traits_type::eq_int_type(c,traits_type::eof()))*pptr()=traits_type::to_char_type(c),pbump(1);return traits_type::not_eof(c);}
inline void pc(char c){if(pptr()==epptr()&&traits_type::eq_int_type(overflow(),traits_type::eof()))return;*pptr()=c;pbump(1);}inline void ps(const char*s,size_t n){while(n){size_t k=static_cast<size_t>(epptr()-pptr());if(!k){if(traits_type::eq_int_type(overflow(),traits_type::eof()))return;k=static_cast<size_t>(epptr()-pptr());}k=min(k,n);memcpy(pptr(),s,k);pbump(static_cast<int>(k));s+=k;n-=k;}}
}ob;
struct FastIn:istream{
FastIn():istream(&ib){}using istream::operator>>;template<class T>inline FastIn&go(T&x){if(!ib.read(x))setstate(ib.eofed?ios::eofbit|ios::failbit:ios::failbit);else if(ib.eofed)setstate(ios::eofbit);return *this;}inline FastIn&operator>>(short&x){return go(x);}inline FastIn&operator>>(us&x){return go(x);}inline FastIn&operator>>(int&x){return go(x);}inline FastIn&operator>>(unsigned&x){return go(x);}inline FastIn&operator>>(long&x){return go(x);}inline FastIn&operator>>(unsigned long&x){return go(x);}inline FastIn&operator>>(ll&x){return go(x);}inline FastIn&operator>>(ull&x){return go(x);}inline FastIn&operator>>(hint&x){return go(x);}inline FastIn&operator>>(uhint&x){return go(x);}inline FastIn&operator>>(char&x){return go(x);}inline FastIn&operator>>(string&x){return go(x);}inline FastIn&operator>>(float&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(long double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(bool&x){int y=0;go(y);x=y!=0;return *this;}
}fin;
struct FastOut:ostream{
FastOut():ostream(&ob){}using ostream::operator<<;template<class U>inline FastOut&uo(U x){char s[64];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);while(n)ob.pc(s[--n]);return *this;}template<class T>inline FastOut&so(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}typedef typename make_unsigned<T>::type U;U y;if(x<0){ob.pc('-');y=U(0)-static_cast<U>(x);}else y=static_cast<U>(x);return uo(y);}template<class T>inline FastOut&un(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}
inline FastOut&operator<<(short x){return so(x);}inline FastOut&operator<<(us x){return un(x);}inline FastOut&operator<<(int x){return so(x);}inline FastOut&operator<<(unsigned x){return un(x);}inline FastOut&operator<<(long x){return so(x);}inline FastOut&operator<<(unsigned long x){return un(x);}inline FastOut&operator<<(ll x){return so(x);}inline FastOut&operator<<(ull x){return un(x);}inline FastOut&operator<<(bool x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}ob.pc(x?'1':'0');return *this;}inline FastOut&operator<<(char c){if(width()!=0){static_cast<ostream&>(*this)<<c;return *this;}ob.pc(c);return *this;}inline FastOut&operator<<(const char*s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s,strlen(s));return *this;}inline FastOut&operator<<(const string&s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s.data(),s.size());return *this;}inline FastOut&operator<<(float x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(double x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(long double x){static_cast<ostream&>(*this)<<x;return *this;}
inline FastOut&operator<<(hint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}uhint y;if(x<0){ob.pc('-');y=uhint(0)-static_cast<uhint>(x);}else y=static_cast<uhint>(x);return uo(y);}inline FastOut&operator<<(uhint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}FastOut&operator<<(ios_base&(*f)(ios_base&)){f(*this);return *this;}FastOut&operator<<(ostream&(*f)(ostream&)){f(*this);return *this;}FastOut&operator<<(ios&(*f)(ios&)){f(*this);return *this;}
}fout;
}
ostream& out128(ostream&out,uhint x,bool neg){char s[48];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);streamsize w=out.width(0),k=max<streamsize>(0,w-n-neg);char f=out.fill();ios::fmtflags a=out.flags()&ios::adjustfield;if(a==ios::left){if(neg)out.put('-');while(n)out.put(s[--n]);while(k--)out.put(f);}else if(a==ios::internal&&neg){out.put('-');while(k--)out.put(f);while(n)out.put(s[--n]);}else{while(k--)out.put(f);if(neg)out.put('-');while(n)out.put(s[--n]);}return out;}
ostream& operator<<(ostream&out,hint x){bool neg=x<0;return out128(out,neg?uhint(0)-static_cast<uhint>(x):static_cast<uhint>(x),neg);}ostream& operator<<(ostream&out,uhint x){return out128(out,x,false);}
#define cin mystl::fin
#define cout mystl::fout
namespace my{
using poly=vector<ull>;
ull P;
ull ni,r2,one;
pref ull red(u128 x){
ull z=(x+(u128)((ull)x*ni)*P)>>64;
if(z>=P)z-=P;
return z;
}
pref ull enc(ull x){return red((u128)x*r2);}
pref ull mm(ull x,ull y){return red((u128)x*y);}
pref void setmod(ull p){
P=p;ni=1;
up(i,1,6)ni*=2-P*ni;
ni=-ni;
one=((u128)1<<64)%P;
r2=(u128)one*one%P;
}
int B;
pref ull mul(ull a,ull b,ull p){
return (u128)a*b%p;
}
pref ull power(ull a,ull b,ull p){
ull ans=1;
while(b){
if(b&1)ans=mul(ans,a,p);
a=mul(a,a,p),b>>=1;
}
return ans;
}
pref ull gcd(ull a,ull b){
while(b){
ull t=a%b;
a=b,b=t;
}
return a;
}
bool prime(ull n){
if(n<2)return false;
for(int p:{2,3,5,7,11,13,17,19,23,29,31,37})
if(n%p==0)return n==(ull)p;
ull d=n-1;
int s=0;
while(!(d&1))d>>=1,s++;
for(ull a:{2ull,325ull,9375ull,28178ull,450775ull,9780504ull,1795265022ull}){
if(a%n==0)continue;
ull x=power(a%n,d,n);
if(x==1||x==n-1)continue;
bool ok=false;
up(i,1,s-1){
x=mul(x,x,n);
if(x==n-1){
ok=true;
break;
}
}
if(!ok)return false;
}
return true;
}
pref void trim(poly&a){
while(!a.empty()&&!a.back())a.pop_back();
}
template<u32 M,u32 G>struct Cntt{
using NT=pd::NTT<M,G>;
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
__attribute__((target("avx2"))) static vector<u32> fast(vector<u32>a,vector<u32>b){
using A=pd::AN<M,G>;
int n=a.size(),l=__builtin_ctz((u32)n);
A::fw2(l,a.data(),b.data());
for(int i=0;i<n;i+=8)
A::st(a.data()+i,A::mv(A::ld(a.data()+i),A::ld(b.data()+i),false));
A::iv(l,a.data(),A::rr().r);
for(auto&x:a)if(x>=M)x-=M;
return a;
}
#endif
static vector<u32> run(const poly&a,const poly&b,int n){
vector<u32>x(n),y(n);
up(i,0,(int)a.size()-1)x[i]=a[i]%M;
up(i,0,(int)b.size()-1)y[i]=b[i]%M;
#if (defined(__x86_64__)||defined(__i386__))&&(defined(__GNUC__)||defined(__clang__))
if(NT::avx()&&n>=8)return fast(move(x),move(y));
#endif
NT::ntt(x,0),NT::ntt(y,0);
up(i,0,n-1)x[i]=NT::mul(x[i],y[i]);
NT::ntt(x,1);
return x;
}
};
poly conv(const poly&a,const poly&b,int len=0,int mode=0){
if(a.empty()||b.empty())return {};
int n=a.size(),m=b.size(),sz=len?len:n+m-1;
poly c(sz);
if(min(n,m)<=24){
up(k,0,n+m-2){
u128 v=0;
up(i,max(0,k-m+1),min(k,n-1))v+=(u128)a[i]*b[k-i];
if(len){ull &x=c[k&(len-1)];ull z=red(v);if(z>=P)z-=P;x+=z;if(x>=P)x-=P;}
else{c[k]=red(v);if(c[k]>=P)c[k]-=P;}
}
return c;
}
int cap=1;
while(cap<sz)cap<<=1;
auto a0=Cntt<998244353,3>::run(a,b,cap);
auto a1=Cntt<754974721,11>::run(a,b,cap);
auto a2=Cntt<469762049,3>::run(a,b,cap);
auto a3=Cntt<167772161,3>::run(a,b,cap);
auto a4=Cntt<880803841,26>::run(a,b,cap);
ull w1=998244353ull%P,w2=(u128)w1*754974721%P;
ull w3=(u128)w2*469762049%P,w4=(u128)w3*167772161%P;
up(i,0,sz-1){
ull d0=a0[i];
ull z1=(d0)%754974721;
ull d1=(a1[i]+754974721ull-z1)*416537774ull%754974721;
ull z2=(d0+58720255ull*d1)%469762049;
ull d2=(a2[i]+469762049ull-z2)*429847628ull%469762049;
ull z3=(d0+159383548ull*d1+113246226ull*d2)%167772161;
ull d3=(a3[i]+167772161ull-z3)*159325719ull%167772161;
ull z4=(d0+117440512ull*d1+16777216ull*d2+477591416ull*d3)%880803841;
ull d4=(a4[i]+880803841ull-z4)*77717847ull%880803841;
c[i]=red(d0+(u128)w1*d1+(u128)w2*d2+(u128)w3*d3+(u128)w4*d4);
}
return c;
}
poly fac,ifac;
ull shift(const poly&a,ull x,int m,poly&ans){
int d=(int)a.size()-1,len=d+m;
poly v(len),pre(len+1),iv(len),w(d+1);
ull z=enc((x+P-d)%P);
pre[0]=one;
up(i,0,len-1){
v[i]=z;
pre[i+1]=mm(pre[i],z);
z+=one;if(z>=P)z-=P;
}
if(gcd(pre[len],P)!=1){
for(ull x:v){
ull g=gcd(x,P);
if(g>1&&g<P)return g;
}
}
ull t=enc(pd::I64(red(pre[len]),P));
dn(i,len-1,0){
iv[i]=mm(t,pre[i]);
t=mm(t,v[i]);
}
up(i,0,d){
w[i]=mm(mm(a[i],ifac[i]),ifac[d-i]);
if((d-i)&1)w[i]=w[i]?P-w[i]:0;
}
int cap=1;
while(cap<len)cap<<=1;
poly c=conv(w,iv,cap);
ans.resize(m);
t=pre[d+1];
up(i,0,m-1){
ans[i]=mm(t,c[d+i]);
if(i+1<m)t=mm(mm(t,v[d+i+1]),iv[i]);
}
return 0;
}
ull check(const poly&f,int d,ull span,bool last){
const int rs[8]={1,7,11,13,17,19,23,29};
for(int l=0;l<(int)f.size();l+=128){
int r=min(l+128,(int)f.size());
ull v=one;
up(i,l,r-1)v=mm(v,f[i]);
ull g=gcd(v,P);
if(g==1)continue;
if(g<P)return g;
up(i,l,r-1){
g=gcd(f[i],P);
if(g>1&&g<P)return g;
if(g==P)up(j,0,d/8-1)for(int z:rs){
ll x=(ll)(i*span+30ull*j+z)-(last?0:15ll*d/8);
g=gcd(x<0?-x:x,P);
if(g>1&&g<P)return g;
}
}
}
return 0;
}
ull factor(ull n){
setmod(n);B=8;
while((u128)B*B*B*B*900<(u128)n*64)B<<=1;
B*=2;
ull lim=sqrtl((long double)n);
while((u128)(lim+1)*(lim+1)<=n)++lim;
while((u128)lim*lim>n)--lim;
ull span=(ull)B*30/8;
int cnt=lim/span+1;
const int rs[8]={1,7,11,13,17,19,23,29};
static vector<int>pr;
if(pr.empty()){
static bool mark[65540];
up(i,2,65538)if(!mark[i]){
pr.push_back(i);
for(int j=i+i;j<=65538;j+=i)mark[j]=true;
}
}
for(int p:pr){if(p>2*B+2)break;if(n%p==0)return p;}
int H=B/2;
fac.resize(H+1),ifac.resize(H+1);
fac[0]=one;
up(i,1,H)fac[i]=mm(fac[i-1],enc(i));
ifac[H]=enc(pd::I64(red(fac[H]),P));
dn(i,H,1)ifac[i-1]=mm(ifac[i],enc(i));
ull ib=pd::I64(2*B,P),half=(P+1)/2;
poly f(5,one);
up(i,0,4)for(int r:rs)f[i]=mm(f[i],enc((i*span+r+P-15)%P));
for(int d=8;d<B;d<<=1){
ull g=check(f,d,span,false);
if(g)return g;
poly a(d+1),b;
up(i,0,d)a[i]=f[abs(i-d/2)];
bool last=2*d==B;
ull x=mul(d,ib,P);
int m;
if(last){x=(x+half+P-cnt+d/2)%P;m=2*cnt;}
else{x=(x+P-d/2)%P;m=2*d+1;}
g=shift(a,x,m,b);
if(g)return g;
if(last){
f.resize(cnt);
up(i,0,cnt-1)f[i]=mm(b[cnt+i],b[cnt-1-i]);
}else{
f.resize(d+1);
up(i,0,d)f[i]=mm(b[d+i],b[d-i]);
}
}
return check(f,B,span,true);
}
ull solve(ull n){
ull ans=0;
up(p,2,100)if(n%p==0){
ans=p;
while(n%p==0)n/=p;
}
if(n==1)return ans;
if(prime(n))return max(ans,n);
ull r=sqrtl((long double)n);
while((u128)r*r>n)--r;
while((u128)(r+1)*(r+1)<=n)++r;
if((u128)r*r==n)return max(ans,solve(r));
r=cbrtl((long double)n);
while((u128)r*r*r>n)--r;
while((u128)(r+1)*(r+1)*(r+1)<=n)++r;
if((u128)r*r*r==n)return max(ans,solve(r));
ull p=factor(n);
return max(ans,max(solve(p),solve(n/p)));
}
pref void SOLVE(){
ull n;cin>>n;
if(prime(n))cout<<"Prime\n";
else cout<<solve(n)<<'\n';
}
}
int main(){
int T;cin>>T;
while(T--)my::SOLVE();
return 0;
}:::
终于卡过了！！！
哦，对恭喜我自己发明带