贴个老板子
namespace Modsqrt{
#define ll long long
ll w2;
struct CP{
ll x,y;
CP() {}
CP(ll x,ll y):x(x),y(y) {}
CP operator *(const CP &a) const{
ll X=(x*a.x+y*a.y%mod*w2)%mod;
ll Y=(x*a.y+y*a.x)%mod;
return CP(X,Y);
}
};
inline CP CP_qpow(CP a,int b){
CP ans=CP(1,0);
for(;b;b>>=1){
if(b&1)ans=ans*a;
a=a*a;
}
return ans;
}
inline ll modsqrt(ll x){
srand(time(0));
ll y=1ll*rand()*rand()%mod;
while(qpow(w2=(y*y+mod-x)%mod,(mod-1)>>1)==1)
y=1ll*rand()*rand()%mod;
CP ans=CP_qpow(CP(y,1),(mod+1)>>1);
return min(ans.x,mod-ans.x);
}
#undef ll
}
using namespace Modsqrt;
long long inv[maxn],frac[maxn],invf[maxn];
inline void Init_Inv(int N){
frac[0]=1;
for(int i=1;i<=N;i++)frac[i]=frac[i-1]*i%mod;
invf[N]=qpow(frac[N],mod-2);
for(int i=N;i>=1;i--)invf[i-1]=invf[i]*i%mod;
for(int i=1;i<=N;i++)inv[i]=invf[i]*frac[i-1]%mod;
}
inline void init(int N){
Init_Inv(N);
}
namespace Polyn{
#define G 3
#define ll long long
int lstn,rev[maxn];
long long g[2][33];
inline void cpy(int N,ll *a,ll *b){
for(int i=0;i<N;i++)a[i]=b[i];
}
inline void clr(int N,ll *a){
for(int i=0;i<N;i++)a[i]=0;
}
inline void mve(int N,int len,ll *a){
if(!len)return;
if(len>0){
for(int i=N-1;i>=len;i--)a[i]=a[i-len];
for(int i=len-1;i>=0;i--)a[i]=0;
}
else {
len=-len;
for(int i=0;i<N-len;i++)a[i]=a[i+len];
for(int i=N-len;i<N;i++)a[i]=0;
}
}
inline void Init_G(){
g[0][23]=qpow(G,(mod-1)/(1<<23));
g[1][23]=qpow(g[0][23],mod-2);
for(int i=22;i>=1;i--){
g[0][i]=g[0][i+1]*g[0][i+1]%mod;
g[1][i]=g[1][i+1]*g[1][i+1]%mod;
}
}
inline void init(int N){
if(lstn==N)return;
lstn=N;
for(int i=1;i<N;i++)
rev[i]=(rev[(i>>1)]>>1)|(i&1?(N>>1):0);
}
inline void Der(int N,ll *f){
for(int i=1;i<N;i++)
f[i-1]=f[i]*i%mod;
f[N-1]=0;
}
inline void Int(int N,ll *f){
for(int i=N;i;i--)
f[i]=f[i-1]*inv[i]%mod;
f[0]=0;
}
inline void NTT(int N,ll *f,bool flg){
for(int i=1;i<N;i++)
if(i<rev[i])swap(f[i],f[rev[i]]);
for(int i=1,lg=1;i<N;i<<=1,lg++){
for(int p=(i<<1),j=0;j<N;j+=p){
ll ng=1;
for(int k=0;k<i;k++){
ll val=ng*f[i+j+k]%mod;
f[i+j+k]=(f[j+k]+mod-val)%mod;
(f[j+k]+=val)%=mod;
(ng*=g[flg][lg])%=mod;
}
}
}
if(!flg)return;
ll invn=qpow(N,mod-2);
for(int i=0;i<N;i++)
(f[i]*=invn)%=mod;
}
inline void Mul(int n,ll *a,ll b){
for(int i=0;i<n;i++)(a[i]*=b)%=mod;
}
inline void Mul(int n,ll *a,ll *b,int na=-1,int nb=-1,int len=-1){
int N=1;
for(;N<n;N<<=1);
init(N);
if(na<0)na=n;
if(nb<0)nb=n;
clr(N-na,a+na),clr(N-nb,b+nb);
NTT(N,a,0),NTT(N,b,0);
for(int i=0;i<N;i++)
(a[i]*=b[i])%=mod;
NTT(N,a,1);
if(len<0)return;
clr(N-len,a+len);
}
inline void Inv(int n,ll *f,ll *ans){
static ll A[maxn],B[maxn];
int N=1;
for(;N<n;N<<=1);
clr(N,A),clr(N,B),clr(N,ans);
ans[0]=qpow(f[0],mod-2);
for(int len=2;len<=N;len<<=1){
cpy(len>>1,A,ans);
cpy(len,B,f);
Mul(len,A,B);
clr(len>>1,A);
cpy(len,B,ans);
Mul(len,A,B);
for(int i=(len>>1);i<len;i++)
ans[i]=(ans[i]*2+mod-A[i])%mod;
}
}
inline void Sqrt(int n,ll *f,ll *ans){
static ll A[maxn],B[maxn];
int N=1;
for(;N<n;N<<=1);
clr(N,A),clr(N,B),clr(N,ans);
ans[0]=modsqrt(f[0]);
for(int len=2;len<=N;len<<=1){
Inv(len,ans,A);
cpy(len,B,f);
Mul((len<<1),A,B,len,len,len);
for(int i=0;i<len;i++)
ans[i]=(ans[i]+A[i])*inv2%mod;
}
clr(N-n,ans+n);
}
inline void Ln(int n,ll *f,ll *ans){
static ll A[maxn];
int N=1;
for(;N<(n<<1);N<<=1);
clr(N,A),clr(N,ans);
cpy(n,ans,f);
Der(n,ans);
Inv(n,f,A);
Mul(n+n-1,ans,A,n);
Int(n,ans);
}
inline void Exp(int n,ll *f,ll *ans){
static ll A[maxn],B[maxn];
int N=1;
for(;N<n;N<<=1);
clr(N,A),clr(N,B),clr(N,ans);
ans[0]=1;
for(int len=2;len<=N;len<<=1){
cpy(len,B,f);
B[0]++;
Ln(len,ans,A);
for(int i=0;i<len;i++)
(B[i]+=mod-A[i])%=mod;
Mul((len<<1),ans,B,len,len,len);
}
clr(N-n,ans+n);
}
inline void Pow(int n,int k,int k1,int MOD,ll *f,ll *ans){
if(n==1)cpy(n,ans,f);
static ll A[maxn];
int x=0;
int N=1;
for(;N<n;N<<=1);
clr(N,A),clr(N,ans);
for(;x<n&&!f[x];x++);
if(1ll*x*k1>=MOD)return;
cpy(n,ans,f);
mve(n,-x,ans);
int m=MOD-x;
if(ans[0]>1){
ll inv0=qpow(ans[0],mod-2);
for(int i=0;i<n-x;i++)
(ans[i]*=inv0)%=mod;
}
Ln(m,ans,A);
Mul(m,A,k);
Exp(m,A,ans);
mve(MOD,x*k1,ans);
if(f[x]>1)Mul(MOD,ans,qpow(f[x],k1));
}
#undef ll
#undef G
}
long long A[maxn];
struct P{
#define ll long long
int n;
ll f[maxn];
inline void Read(){
for(int i=0;i<n;i++)
f[i]=read<ll>();
}
inline void Print(){
for(int i=0;i<n;i++)
printf("%lld ",f[i]);
puts("");
}
ll& operator [](const int &x){
return f[x];
}
inline P Mod(int N){
P c;
c.n=N;
for(int i=0;i<N;i++)
c[i]=f[i];
return c;
}
inline P R(){
P c;
c.n=n;
for(int i=0;i<n;i++)
c[i]=f[n-i-1];
return c;
}
inline P Der(){
P c;
c.n=n-1;
for(int i=1;i<n;i++)
c[i-1]=f[i]*i%mod;
return c;
}
inline P Int(){
P c;
c.n=n+1;
for(int i=1;i<=n;i++)
c[i]=f[i-1]*inv[i]%mod;
c[0]=0;
return c;
}
inline P Inv(){
P c;
c.n=n;
Polyn::Inv(n,f,c.f);
return c;
}
inline P Sqrt(){
P c;
c.n=n;
Polyn::Sqrt(n,f,c.f);
return c;
}
inline P Ln(){
P c;
c.n=n;
Polyn::Ln(n,f,c.f);
return c;
}
inline P Exp(){
P c;
c.n=n;
Polyn::Exp(n,f,c.f);
return c;
}
inline P Pow(int k,int k1,int MOD){
P c;
c.n=n;
Polyn::Pow(n,k,k1,MOD,f,c.f);
return c;
}
P operator -(){
P c;
c.n=n;
for(int i=0;i<c.n;i++)c[i]=mod-f[i];
return c;
}
P operator +(const ll b){
P c;
c.n=n;
for(int i=0;i<c.n;i++)c[i]=f[i];
(c[0]+=b)%=mod;
return c;
}
P operator +(P b){
P c;
c.n=max(n,b.n);
for(int i=0;i<c.n;i++)
c[i]=(f[i]+b[i])%mod;
return c;
}
P operator -(const ll b){
P c;
c.n=n;
for(int i=0;i<c.n;i++)c[i]=f[i];
(c[0]+=mod-b%mod)%=mod;
return c;
}
P operator -(P b){
P c;
c.n=max(n,b.n);
for(int i=0;i<c.n;i++)
c[i]=(f[i]+mod-b[i])%mod;
return c;
}
P operator *(const ll num){
P c;
c.n=n;
for(int i=0;i<n;i++)
c[i]=f[i]*num%mod;
return c;
}
P operator *(P b){
P c;
c.n=n+b.n-1;
for(int i=0;i<n;i++)c[i]=f[i];
for(int i=0;i<b.n;i++)A[i]=b[i];
int N=1;
for(;N<c.n;N<<=1);
for(int i=n;i<N;i++)c[i]=0;
for(int i=b.n;i<N;i++)A[i]=0;
Polyn::Mul(c.n,c.f,A);
return c;
}
#undef ll
};