struct Polynoial{
struct Complex{
double x,y;
Complex(double _x = 0.0,double _y = 0.0){
x = _x;
y = _y;
}
Complex operator-(const Complex &rhs) const{
return Complex(x-rhs.x,y-rhs.y);
}
Complex operator+(const Complex &rhs) const{
return Complex(x+rhs.x,y+rhs.y);
}
Complex operator*(const Complex &rhs) const{
return Complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);
}
};
int getSize(int n) {
int size = 1;
while (size < n) size <<= 1;
return size;
}
void change(vector<Complex>&a,int n){
for(int i = 1,j = n/2;i < n-1;i++){
if(i < j){
swap(a[i],a[j]);
}
int k = n/2;
while(j >= k){
j -= k;
k /= 2;
}
if(j < k)j += k;
}
}
void fft(vector<Complex>&a,int n,int opt){
change(a,n);
for(int h = 2;h <= n;h*=2){
Complex wn(cos(2*PI/h),sin(opt*2*PI/h)); // 修正:PI/h 而不是 PI/n
for(int j = 0;j < n;j+=h){
Complex w(1,0);
for(int k = j;k < j+h/2;k++){
Complex u = a[k];
Complex t = w*a[k+h/2];
a[k]=u+t;
a[k+h/2]=u-t;
w=w*wn;
}
}
}
if(opt == -1){
for(int i = 0;i < n;i++){
a[i].x /= n;
}
}
}
vector<int> multiply(vector<int>& a, vector<int>& b) {
int size = getSize(a.size() + b.size() - 1);
vector<Complex> fa(size), fb(size);
for(int i = 0; i < (int)a.size(); i++) fa[i] = Complex(a[i], 0);
for(int i = 0; i < (int)b.size(); i++) fb[i] = Complex(b[i], 0);
for(int i = a.size(); i < size; i++) fa[i] = Complex(0, 0);
for(int i = b.size(); i < size; i++) fb[i] = Complex(0, 0);
fft(fa, size, 1);
fft(fb, size, 1);
for(int i = 0; i < size; i++) {
fa[i] = fa[i] * fb[i];
}
fft(fa, size, -1);
vector<int> res(size);
for(int i = 0; i < size; i++) {
res[i] = (int)(fa[i].x + 0.5);
}
return res;
}
};#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,invn,invG,f[N],g[N],g0[N],gm[N],f0[N],fm[N],tr[N],jc[N],inv[N],invjc[N];LL m;
template<typename T>inline void in(T &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,LL k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int Inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
for(Re st=0;st<n;st+=p)
for(Re i=st,base=1;i<=st+len-1;++i){
Re tmp=(LL)base*f[len+i]%P;
f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
}
}
}
inline void times(Re *f,Re n,Re *g,Re m){
for(m+=n,n=1;n<=m;n<<=1);invn=Inv(n),invG=Inv(G);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=0;i<=n;++i)in(f0[i]);
invjc[1]=invjc[0]=inv[1]=jc[1]=jc[0]=1;
for(Re i=2;i<=n+1;++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P,jc[i]=(LL)jc[i-1]*i%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
for(Re i=0;i<=n;++i)f[i]=(LL)jc[n-i]*f0[n-i]%P,g[i]=invjc[i];
times(f,n,g,n);
for(Re i=0;i<=n;++i)g0[i]=(LL)f[n-i]*invjc[i]%P;
// for(Re i=0;i<=n;++i)printf("%d ",g0[i]);puts("");
for(Re i=0;i<=n;++i)gm[i]=(LL)g0[i]*mi(inv[i+1],m)%P;
// for(Re i=0;i<=n;++i)printf("%d ",gm[i]);puts("");
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(Re i=0;i<=n;++i)f[i]=(LL)jc[n-i]*gm[n-i]%P,g[i]=(LL)invjc[i]*((i&1)?P-1:1)%P;
times(f,n,g,n);
for(Re i=0;i<=n;++i)fm[i]=(LL)f[n-i]*invjc[i]%P;
for(Re i=0;i<=n;++i)printf("%d ",fm[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+5;
const LD Pi=acos(-1);
int n,m,tr[N],Ans[N];char s1[N>>1],s2[N>>1];
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct CP{
LD x,y;
CP(LD X=0,LD Y=0){x=X,y=Y;}
inline CP operator+(const CP &O)const{return CP(x+O.x,y+O.y);}
inline CP operator-(const CP &O)const{return CP(x-O.x,y-O.y);}
inline CP operator*(const CP &O)const{return CP(x*O.x-y*O.y,x*O.y+y*O.x);}
inline CP operator*=(const CP &O){return *this=*this*O;}
}f[N],g[N];
inline void FFT(CP *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1;
CP w1(cos(2*Pi/p),sin(2*Pi/p));
if(op)w1.y*=-1;
for(Re st=0;st<n;st+=p){
CP base(1,0);
for(Re i=st;i<=st+len-1;++i){
CP tmp=f[len+i]*base;
f[len+i]=f[i]-tmp,f[i]=f[i]+tmp,base*=w1;
}
}
}
}
int main(){
// freopen("123.txt","r",stdin);
scanf("%s%s",s1,s2),n=strlen(s1),m=strlen(s2);
for(Re i=0;i<n;++i)f[i].x=s1[n-i-1]-'0';
for(Re i=0;i<m;++i)g[i].x=s2[m-i-1]-'0';
for(m+=n,n=1;n<=m;n<<=1);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
FFT(f,n,0),FFT(g,n,0);
for(Re i=0;i<n;++i)f[i]*=g[i];
FFT(f,n,1);
for(Re i=0;i<=m;++i){
Ans[i]+=(int)(f[i].x/n+0.5);
if(Ans[i]>9)Ans[i+1]+=Ans[i]/10,Ans[i]%=10,m+=(i==m);
}
while(!Ans[m]&&m>=1)--m;
for(Re i=m;i>=0;--i)printf("%d",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=131072+3,P=998244353,G=3;
int n,m,invn,invG,f[N],g[N],A[N],tr[N],ans[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
for(Re st=0;st<n;st+=p)
for(Re i=st,base=1;i<=st+len-1;++i){
Re tmp=(LL)base*f[i+len]%P;
f[i+len]=(f[i]-tmp+P)%P;
f[i]=(f[i]+tmp)%P;
base=(LL)base*w1%P;
}
}
}
inline void times(Re *f,Re n,Re *g,Re m){
for(n=1;n<=m;n<<=1);
for(Re i=m+1;i<=n;++i)f[i]=g[i]=0;
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);
for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
inline void CDQ(Re L,Re R){
if(L==R)return;
Re mid=L+R>>1;CDQ(L,mid);
for(Re i=L;i<=R;++i)g[i-L]=A[i-L];
for(Re i=L;i<=mid;++i)f[i-L]=ans[i];
for(Re i=mid+1;i<=R;++i)f[i-L]=0;
times(f,mid-L,g,R-L);
for(Re i=mid+1;i<=R;++i)(ans[i]+=f[i-L])%=P;
CDQ(mid+1,R);
}
int main(){
// freopen("123.txt","r",stdin);
in(n),invG=inv(G);
for(Re i=1;i<n;++i)in(A[i]);
ans[0]=1,CDQ(0,n-1);
for(Re i=0;i<n;++i)printf("%d ",ans[i]);
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+3;
const LD Pi=acos(-1);
int n,m,tr[N];
inline void in(Re &x){
Re fu=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=fu?-x:x;
}
struct CP{
LD x,y;CP(LD X=0,LD Y=0){x=X,y=Y;}
inline CP operator+(const CP &O)const{return CP(x+O.x,y+O.y);}
inline CP operator-(const CP &O)const{return CP(x-O.x,y-O.y);}
inline CP operator*(const CP &O)const{return CP(x*O.x-y*O.y,x*O.y+y*O.x);}//(ac-bd,bc+ad)
inline CP operator/(const CP &O)const{
LD tmp=O.x*O.x+O.y*O.y;//tmp=c^2+d^2
return CP((x*O.x+y*O.y)/tmp,(y*O.x-x*O.y)/tmp);//( (ac+bd)/tmp,(bc-ad)/tmp )
}
inline CP operator*=(const CP &O){return *this=*this*O;}
}f[N],g[N];
inline void FFT(CP *f,Re n,Re op){//op=0:DFT, op=1:IDFT
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1;CP w1(cos(2*Pi/p),sin(2*Pi/p));
if(op)w1.y*=-1;
for(Re st=0;st<n;st+=p){
CP base(1,0);
for(Re i=st;i<=st+len-1;++i){
CP tmp=base*f[len+i];
f[len+i]=f[i]-tmp,f[i]=f[i]+tmp,base*=w1;
}
}
}
}
inline void times(CP *f,Re n,CP *g,Re m){
for(m+=n,n=1;n<=m;n<<=1);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
FFT(f,n,0),FFT(g,n,0);
for(Re i=0;i<n;++i)f[i]*=g[i];
FFT(f,n,1);
for(Re i=0;i<=m;++i)f[i].x/=n;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=0;i<=n;++i)scanf("%lf",&f[i].x);
for(Re i=0;i<=m;++i)scanf("%lf",&g[i].x);
times(f,n,g,m);
for(Re i=0;i<=n+m;++i)printf("%d ",(int)(f[i].x+0.5));
}
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+3,P=998244353,G=3;
int n,m,invn,invG,f[N],g[N],tr[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
for(Re st=0;st<n;st+=p)
for(Re i=st,base=1;i<=st+len-1;++i){
Re tmp=(LL)base*f[len+i]%P;
f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
}
}
}
inline void times(Re *f,Re n,Re *g,Re m){
for(m+=n,n=1;n<=m;n<<=1);invn=inv(n),invG=inv(G);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m);
for(Re i=0;i<=n;++i)in(f[i]);
for(Re i=0;i<=m;++i)in(g[i]);
times(f,n,g,m);
for(Re i=0;i<=n+m;++i)printf("%d ",f[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=131072+3,P=998244353;
int n,m,inv2,A[N],B[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int inv(Re x){
Re s=1,k=P-2;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
int id,f[N],g[N];
inline void FWT(Re *f,Re n,Re op){
for(Re p=2;p<=n;p<<=1)
for(Re st=1,len=p>>1;st<n;st+=p)
for(Re j=st;j<=st+len-1;++j)
if(id==1)(f[j+len]+=(op?P-f[j]:f[j]))%=P;
else if(id==2)(f[j]+=(op?P-f[j+len]:f[j+len]))%=P;
else{
Re g0=f[j],g1=f[j+len];
f[j]=(g0+g1)%P,f[j+len]=(g0-g1+P)%P;
if(op)f[j]=(LL)f[j]*inv2%P,f[j+len]=(LL)f[j+len]*inv2%P;
}
}
inline void sakura(Re *A,Re *B,Re n,Re id_){
for(Re i=1;i<=n;++i)f[i]=A[i],g[i]=B[i];id=id_;
FWT(f,n,0),FWT(g,n,0);
for(Re i=1;i<=n;++i)f[i]=(LL)f[i]*g[i]%P;
FWT(f,n,1);
for(Re i=1;i<=n;++i)printf("%d ",f[i]);puts("");
}
int main(){
// freopen("123.txt","r",stdin);
in(n),n=(1<<n),inv2=inv(2);
for(Re i=1;i<=n;++i)in(A[i]);
for(Re i=1;i<=n;++i)in(B[i]);
sakura(A,B,n,1),sakura(A,B,n,2),sakura(A,B,n,3);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3,phi=P-1;
inline void in(Re &x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
inline int in_(){
int f=0;LL x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+(ch^48),x%=P,ch=getchar();
return x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
for(Re i=1;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1)
for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
for(Re i=st,base=1;i<=st+len-1;++i){
Re tmp=(LL)f[i+len]*base%P;
f[i+len]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
}
}
inline void times(Re *f,Re n,Re *g,Re m){
Re n_=n,m_=m;
for(m+=n,n=1;n<=m;n<<=1);invG=inv(G);
for(Re i=n_+1;i<n;++i)f[i]=0;
for(Re i=m_+1;i<n;++i)g[i]=0;
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);Re invn=inv(n);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int c[N];
inline void polymi(Re *x,Re n,Re k,Re *s){
k%=P,s[0]=1;
for(Re i=1;i<=n;++i)s[i]=0;
while(k){
if(k&1){for(Re i=0;i<=n;++i)c[i]=x[i];times(s,n,c,n);}
for(Re i=0;i<=n;++i)c[i]=x[i];times(x,n,c,n),k>>=1;
}
}
int n,K,f[N],g[N];
int main(){
// freopen("123.txt","r",stdin);
in(n),--n,K=in_();
for(Re i=0;i<=n;++i)in(f[i]);
polymi(f,n,K,g);
for(Re i=0;i<=n;++i)printf("%d ",g[i]);
}
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,A[N],B[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1)
for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
for(Re j=st,base=1;j<=st+len-1;++j){
Re tmp=(LL)base*f[j+len]%P;
f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P,base=(LL)base*w1%P;
}
}
inline void times(Re *f,Re n,Re *g,Re m,Re op=0){
Re n_=n,m_=m;
for(m+=n,n=1;n<=m;n<<=1);invG=inv(G);
for(Re i=n_+1;i<n;++i)f[i]=0;
for(Re i=m_+1;i<n;++i)g[i]=0;
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P*(op?g[i]:1)%P;
NTT(f,n,1);Re invn=inv(n);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int f[N],g[N];
inline void polyinv(Re *a,Re n,Re *b){
if(n==0){b[0]=inv(a[0]);return;}
polyinv(a,n>>1,b);
for(Re i=0;i<=n;++i)f[i]=a[i],g[i]=b[i];
times(f,n,g,n,1);
for(Re i=0;i<=n;++i)b[i]=(2*b[i]%P-f[i]+P)%P;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),--n;
for(Re i=0;i<=n;++i)in(A[i]),A[i]%=P;
polyinv(A,n,B);
for(Re i=0;i<=n;++i)printf("%d ",B[i]);
}
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,A[N],B[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1)
for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
for(Re j=st,base=1;j<=st+len-1;++j){
Re tmp=(LL)base*f[j+len]%P;
f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P,base=(LL)base*w1%P;
}
}
inline void times(Re *f,Re n,Re *g,Re m){
for(n=1;n<=m;n<<=1);invG=inv(G);
for(Re i=m+1;i<n;++i)f[i]=g[i]=0;
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);Re invn=inv(n);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int f[N],g[N],c[N],ans[N];
inline void CDQ(Re L,Re R){
if(L==R)return;
Re mid=L+R>>1;CDQ(L,mid);
for(Re i=L;i<=R;++i)g[i-L]=c[i-L];
for(Re i=L;i<=mid;++i)f[i-L]=ans[i];
for(Re i=mid+1;i<=R;++i)f[i-L]=0;
times(f,mid-L,g,R-L);
for(Re i=mid+1;i<=R;++i)(ans[i]+=f[i-L])%=P;
CDQ(mid+1,R);
}
inline void polyinv(Re *a,Re n,Re *b){
Re tmp=inv(a[0]);c[0]=0;
for(Re i=1;i<=n;++i)c[i]=(LL)(P-a[i])*tmp%P;
ans[0]=tmp,CDQ(0,n);
for(Re i=0;i<=n;++i)b[i]=ans[i];
}
int main(){
// freopen("123.txt","r",stdin);
in(n),--n;
for(Re i=0;i<=n;++i)in(A[i]),A[i]%=P;
polyinv(A,n,B);
for(Re i=0;i<=n;++i)printf("%d ",B[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=1048576+3,P=998244353,G=3;
int n,m,ans,invG,f[N],g[N],tr[N],S1[N],S2[N],PA[N],nex[N];char A[N],B[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void get_next(){
for(Re i=2,j=0;i<=m;++i){
while(j&&B[i]!=B[j+1])j=nex[j];
if(B[i]==B[j+1])++j;nex[i]=j;
}
for(Re i=1;i<=m;++i)printf("%d ",nex[i]);
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
for(Re st=0;st<n;st+=p)
for(Re j=st,base=1;j<=st+len-1;++j){
Re tmp=(LL)base*f[j+len]%P;
f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
base=(LL)base*w1%P;
}
}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
// freopen("123.txt","r",stdin);
scanf("%s%s",A+1,B+1),invG=inv(G);
n=strlen(A+1),m=strlen(B+1);
for(Re i=1;i<=n;++i)f[i]=A[n-i+1]-'A'+1,S1[i]=S1[i-1]+f[i]*f[i];
for(Re i=1;i<=m;++i)g[i]=B[i]-'A'+1,S2[i]=S2[i-1]+g[i]*g[i];
sakura(f,n,g,m);
for(Re i=m;i<=n;++i)PA[n-i+1]=((S1[i]-S1[i-m]+S2[m])%P-2*f[i+1]%P+P)%P;
for(Re i=1;i<=n-m+1;++i)if(PA[i]==0)printf("%d\n",i);
get_next();
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003+3,P=998244353;
inline void in(Re &x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int Inv(Re x){return mi(x,P-2);}
int ff[N],gg[N];
inline void mul(Re *f,Re n,Re a0,Re *g){
for(Re i=0;i<=n;++i)ff[i]=f[i];
g[0]=(LL)a0*ff[0]%P;for(Re i=1;i<=n+1;++i)g[i]=((LL)a0*ff[i]%P+ff[i-1])%P;
}
inline void div(Re *g,Re n,Re a0,Re *f){
for(Re i=0;i<=n;++i)gg[i]=g[i];
f[n-1]=gg[n];for(Re i=n-2;i>=0;--i)f[i]=(gg[i+1]-(LL)a0*f[i+1]%P+P)%P;
}
int fi[N],fmul[N];
inline void Lagrange(Re *x,Re *y,Re n,Re *F){
fmul[0]=P-x[0],fmul[1]=1;
for(Re i=1;i<=n;++i)mul(fmul,i,P-x[i],fmul);
for(Re i=0;i<=n-1;++i)F[i]=0;
for(Re i=0;i<=n;++i){
Re tmp=1;
for(Re j=0;j<=n;++j)if(i!=j)tmp=(LL)tmp*(x[i]-x[j]+P)%P;
tmp=(LL)y[i]*Inv(tmp)%P;
div(fmul,n+1,P-x[i],fi);
for(Re i=0;i<=n;++i)(F[i]+=(LL)tmp*fi[i]%P)%=P;
}
}
int n,X,ans,x[N],y[N],F[N];
int main(){
// freopen("123.txt","r",stdin);
in(n),in(X),--n;
for(Re i=0;i<=n;++i)in(x[i]),in(y[i]);
Lagrange(x,y,n,F);
for(Re i=0,tmp=1;i<=n;++i)(ans+=(LL)F[i]*tmp%P)%=P,tmp=(LL)tmp*X%P;
printf("%d\n",ans);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1048576+3,P=998244353,G=3;
int jc[N],inv[N],invjc[N];
inline void in(Re &x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int Inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
for(Re st=0;st<n;st+=p)
for(Re i=st,base=1;i<=st+len-1;++i){
Re tmp=(LL)base*f[len+i]%P;
f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
}
}
}
inline void times(Re *f,Re n,Re *g,Re m){
for(m+=n,n=1;n<=m;n<<=1);invG=Inv(G);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);Re invn=Inv(n);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int n,m,y[N],f[N],g[N],F[N];
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),jc[0]=jc[1]=inv[1]=invjc[0]=invjc[1]=1;
for(Re i=2;i<=n;++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P,jc[i]=(LL)jc[i-1]*i%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
for(Re i=0;i<=n;++i)in(y[i]),g[i]=(LL)y[i]*((n-i&1)?P-1:1)%P*invjc[i]%P*invjc[n-i]%P;
for(Re i=0;i<=(n<<1);++i)f[i]=Inv(m-n+i);
times(f,n<<1,g,n);Re tmp=1;
for(Re i=m-n;i<=m;++i)tmp=(LL)tmp*i%P;
for(Re i=0;i<=n;tmp=(LL)tmp*Inv(m-n+i)%P,++i,tmp=(LL)tmp*(m+i)%P)F[i]=(LL)tmp*f[n+i]%P;
for(Re i=m;i<=m+n;++i)printf("%d ",F[i-m]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=524288+3,P=998244353,G=3;
int n,m,ans,invG,a[N],b[N],f[N],g[N],tr[N],PA[N];char A[N],B[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
for(Re st=0;st<n;st+=p)
for(Re j=st,base=1;j<=st+len-1;++j){
Re tmp=(LL)base*f[j+len]%P;
f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
base=(LL)base*w1%P;
}
}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
// freopen("123.txt","r",stdin);
in(m),in(n),scanf("%s%s",B+1,A+1),invG=inv(G);
for(Re i=1;i<=n/2;++i)swap(A[i],A[n-i+1]);
for(Re i=1;i<=n;++i)a[i]=(A[i]=='*'?0:A[i]-'a'+1);
for(Re i=1;i<=m;++i)b[i]=(B[i]=='*'?0:B[i]-'a'+1);
for(Re i=1;i<=n;++i)f[i]=(LL)a[i]*a[i]%P*a[i]%P;
for(Re i=1;i<=m;++i)g[i]=b[i];
sakura(f,n,g,m);
for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(Re i=1;i<=n;++i)f[i]=a[i];
for(Re i=1;i<=m;++i)g[i]=(LL)b[i]*b[i]%P*b[i]%P;
sakura(f,n,g,m);
for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(Re i=1;i<=n;++i)f[i]=(LL)a[i]*a[i]%P;
for(Re i=1;i<=m;++i)g[i]=(LL)b[i]*b[i]%P;
sakura(f,n,g,m);
for(Re i=m;i<=n;++i)(PA[n-i+1]+=P-2*f[i+1]%P)%=P;
Re ans=0;
for(Re i=1;i<=n-m+1;++i)ans+=(PA[i]==0);
printf("%d\n",ans);
for(Re i=1;i<=n-m+1;++i)if(PA[i]==0)printf("%d ",i);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,m,K,invG,a[N],b[N],f[N],g[N],S[N],tr[N],PA[N],id[200];char A[N],B[N];
inline void in(Re &x){
int fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int mi(Re x,Re k){
Re s=1;
while(k){
if(k&1)s=(LL)s*x%P;
x=(LL)x*x%P,k>>=1;
}
return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
for(Re p=2;p<=n;p<<=1){
Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
for(Re st=0;st<n;st+=p)
for(Re j=st,base=1;j<=st+len-1;++j){
Re tmp=(LL)base*f[j+len]%P;
f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
base=(LL)base*w1%P;
}
}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,0),NTT(g,n,0);
for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
NTT(f,n,1);
for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(K),scanf("%s%s",A+1,B+1),invG=inv(G);
id['A']=1,id['T']=2,id['C']=3,id['G']=4;
for(Re i=1;i<=n;++i)a[i]=id[A[n-i+1]];
for(Re i=1;i<=m;++i)b[i]=id[B[i]];
for(Re o=1;o<=4;++o){
for(Re i=1;i<=n;++i)S[i]=S[i-1]+(a[i]==o);
for(Re i=1;i<=n;++i)f[i]=(S[i]-S[max(i-K-1,0)]||S[min(i+K,n)]-S[i-1]);
for(Re i=1;i<=m;++i)g[i]=(b[i]==o);
sakura(f,n,g,m);
for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
}
Re ans=0;
for(Re i=1;i<=n-m+1;++i)ans+=(PA[i]==m);
printf("%d\n",ans);
}