#line 1 "library/Template/template.hpp" #include using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() using ll=long long int; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} #line 2 "library/Utility/fastio.hpp" #include class FastIO{ static constexpr int L=1<<16; char rdbuf[L]; int rdLeft=0,rdRight=0; inline void reload(){ int len=rdRight-rdLeft; memmove(rdbuf,rdbuf+rdLeft,len); rdLeft=0,rdRight=len; rdRight+=fread(rdbuf+len,1,L-len,stdin); } inline bool skip(){ for(;;){ while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++; if(rdLeft==rdRight){ reload(); if(rdLeft==rdRight)return false; } else break; } return true; } template::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft='0' and rdbuf[rdLeft]<='9' and rdLeft=rdRight)reload(); x=rdbuf[rdLeft++]; return true; } inline bool _read(string& x){ if(!skip())return false; for(;;){ int pos=rdLeft; while(pos' ')pos++; x.append(rdbuf+rdLeft,pos-rdLeft); if(rdLeft==pos)break; rdLeft=pos; if(rdLeft==rdRight)reload(); else break; } return true; } templateinline bool _read(vector& v){ for(auto& x:v){ if(!_read(x))return false; } return true; } char wtbuf[L],tmp[50]; int wtRight=0; inline void flush(){ fwrite(wtbuf,1,wtRight,stdout); wtRight=0; } inline void _write(const char& x){ if(wtRight>L-32)flush(); wtbuf[wtRight++]=x; } inline void _write(const string& x){ for(auto& c:x)_write(c); } template::value,int> =0>inline void _write(T x){ if(wtRight>L-32)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); if (__builtin_expect(x == std::numeric_limits::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } templateinline void _write(const vector& v){ rep(i,0,v.size()){ if(i)_write(' '); _write(v[i]); } } public: FastIO(){} ~FastIO(){flush();} inline void read(){} template inline void read(Head& head,Tail&... tail){ assert(_read(head)); read(tail...); } templateinline void write(){if(ln)_write('\n');} template inline void write(const Head& head,const Tail&... tail){ if(space)_write(' '); _write(head); write(tail...); } }; /** * @brief Fast IO */ #line 3 "sol.cpp" #line 2 "library/Math/modint.hpp" templatestruct fp { int v; static int get_mod(){return mod;} int inv() const{ int tmp,a=v,b=mod,x=1,y=0; while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y); if(x<0){x+=mod;} return x; } fp(ll x=0){init(x%mod+mod);} fp& init(ll x){v=(x=0); fp res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;} return res;} fp& operator+=(const fp& x){return init(v+x.v);} fp& operator-=(const fp& x){return init(v+mod-x.v);} fp& operator*=(const fp& x){v=ll(v)*x.v%mod; return *this;} fp& operator/=(const fp& x){v=ll(v)*x.inv()%mod; return *this;} fp operator+(const fp& x)const{return fp(*this)+=x;} fp operator-(const fp& x)const{return fp(*this)-=x;} fp operator*(const fp& x)const{return fp(*this)*=x;} fp operator/(const fp& x)const{return fp(*this)/=x;} bool operator==(const fp& x)const{return v==x.v;} bool operator!=(const fp& x)const{return v!=x.v;} friend istream& operator>>(istream& is,fp& x){return is>>x.v;} friend ostream& operator<<(ostream& os,const fp& x){return os<struct factorial { vector Fact,Finv,Inv; factorial(int maxx){ Fact.resize(maxx); Finv.resize(maxx); Inv.resize(maxx); Fact[0]=Fact[1]=Finv[0]=Finv[1]=Inv[1]=1; rep(i,2,maxx){Fact[i]=Fact[i-1]*i;} Finv[maxx-1]=Fact[maxx-1].inv(); for(int i=maxx-1;i>=2;i--){Finv[i-1]=Finv[i]*i; Inv[i]=Finv[i]*Fact[i-1];} } T fact(int n,bool inv=0){if(n<0)return 0; return (inv?Finv[n]:Fact[n]);} T inv(int n){if(n<0)return 0; return Inv[n];} T nPr(int n,int r,bool inv=0){if(n<0||nstruct NTT{ vector rt,irt; NTT(int lg=21){ unsigned m=T::get_mod()-1; T prt=p; rt.resize(lg); irt.resize(lg); rep(k,0,lg){ rt[k]=-prt.pow(m>>(k+2)); irt[k]=rt[k].inv(); } } void ntt(vector& f,bool inv=0){ int n=f.size(); if(inv){ for(int m=1;m>=1;){ T w=1; for(int s=0,t=0;s mult(const vector& a,const vector& b,bool same=0){ if(a.empty() or b.empty())return vector(); int n=a.size()+b.size()-1,m=1<<__lg(n*2-1); vector res(m); rep(i,0,a.size()){res[i]=a[i];} ntt(res); if(same)rep(i,0,m)res[i]*=res[i]; else{ vector c(m); rep(i,0,b.size())c[i]=b[i]; ntt(c); rep(i,0,m)res[i]*=c[i]; } ntt(res,1); res.resize(n); return res; } }; /** * @brief Number Theoretic Transform */ #line 2 "library/FPS/fps.hpp" templatestruct Poly:vector{ Poly(int n=0){this->assign(n,T());} Poly(const vector& f){this->assign(ALL(f));} T eval(const T& x){ T res; for(int i=this->size()-1;i>=0;i--)res*=x,res+=this->at(i); return res; } Poly rev()const{Poly res=*this; reverse(ALL(res)); return res;} void shrink(){while(!this->empty() and this->back()==0)this->pop_back();} vector mult(const vector& a,const vector& b,bool same=0)const{ if(a.empty() or b.empty())return vector(); int n=a.size()+b.size()-1,m=1<<__lg(n*2-1); vector res(m); rep(i,0,a.size())res[i]=a[i]; NTT(res,0); if(same)rep(i,0,m)res[i]*=res[i]; else{ vector c(m); rep(i,0,b.size())c[i]=b[i]; NTT(c,0); rep(i,0,m)res[i]*=c[i]; } NTT(res,1); res.resize(n); return res; } Poly square()const{return Poly(mult(*this,*this,1));} Poly operator-()const{return Poly()-*this;} Poly operator+(const Poly& g)const{return Poly(*this)+=g;} Poly operator+(const T& g)const{return Poly(*this)+=g;} Poly operator-(const Poly& g)const{return Poly(*this)-=g;} Poly operator-(const T& g)const{return Poly(*this)-=g;} Poly operator*(const Poly& g)const{return Poly(*this)*=g;} Poly operator*(const T& g)const{return Poly(*this)*=g;} Poly operator/(const Poly& g)const{return Poly(*this)/=g;} Poly operator%(const Poly& g)const{return Poly(*this)%=g;} Poly& operator+=(const Poly& g){ if(g.size()>this->size())this->resize(g.size()); rep(i,0,g.size()){(*this)[i]+=g[i];} return *this; } Poly& operator+=(const T& g){ if(this->empty())this->push_back(0); (*this)[0]+=g; return *this; } Poly& operator-=(const Poly& g){ if(g.size()>this->size())this->resize(g.size()); rep(i,0,g.size()){(*this)[i]-=g[i];} return *this; } Poly& operator-=(const T& g){ if(this->empty())this->push_back(0); (*this)[0]-=g; return *this; } Poly& operator*=(const Poly& g){ *this=mult(*this,g,0); return *this; } Poly& operator*=(const T& g){ rep(i,0,this->size())(*this)[i]*=g; return *this; } Poly& operator/=(const Poly& g){ if(g.size()>this->size()){ this->clear(); return *this; } Poly g2=g; reverse(ALL(*this)); reverse(ALL(g2)); int n=this->size()-g2.size()+1; this->resize(n); g2.resize(n); *this*=g2.inv(); this->resize(n); reverse(ALL(*this)); shrink(); return *this; } Poly& operator%=(const Poly& g){*this-=*this/g*g; shrink(); return *this;} Poly diff()const{ Poly res(this->size()-1); rep(i,0,res.size())res[i]=(*this)[i+1]*(i+1); return res; } Poly inte()const{ Poly res(this->size()+1); for(int i=res.size()-1;i;i--)res[i]=(*this)[i-1]/i; return res; } Poly log()const{ assert(this->front()==1); const int n=this->size(); Poly res=diff()*inv(); res=res.inte(); res.resize(n); return res; } Poly shift(const int& c)const{ const int n=this->size(); Poly res=*this,g(n); g[0]=1; rep(i,1,n)g[i]=g[i-1]*c/i; vector fact(n,1); rep(i,0,n){ if(i)fact[i]=fact[i-1]*i; res[i]*=fact[i]; } res=res.rev(); res*=g; res.resize(n); res=res.rev(); rep(i,0,n)res[i]/=fact[i]; return res; } Poly inv()const{ const int n=this->size(); Poly res(1); res.front()=T(1)/this->front(); for(int k=1;ksize(); if(n==1)return Poly({T(1)}); Poly b(2),c(1),z1,z2(2); b[0]=c[0]=z2[0]=z2[1]=1; b[1]=(*this)[1]; for(int k=2;k>1)z[i]=0; NTT(z,0); rep(i,0,k)z[i]*=-z1[i]; NTT(z,1); c.insert(c.end(),z.begin()+(k>>1),z.end()); z2=c; z2.resize(k*2); NTT(z2,0); Poly x=*this; x.resize(k); x=x.diff();x.resize(k); NTT(x,0); rep(i,0,k)x[i]*=y[i]; NTT(x,1); Poly bb=b.diff(); rep(i,0,k-1)x[i]-=bb[i]; x.resize(k*2); rep(i,0,k-1){x[k+i]=x[i]; x[i]=0;} NTT(x,0); rep(i,0,k*2)x[i]*=z2[i]; NTT(x,1); x.pop_back(); x=x.inte(); rep(i,k,min(n,k*2))x[i]+=(*this)[i]; rep(i,0,k)x[i]=0; NTT(x,0); rep(i,0,k*2)x[i]*=y[i]; NTT(x,1); b.insert(b.end(),x.begin()+k,x.end()); } b.resize(n); return b; } Poly pow(ll t){ if(t==0){ Poly res(this->size()); res[0]=1; return res; } int n=this->size(),k=0; while(k=n)return res; n-=t*k; Poly g(n); T c=(*this)[k],ic=c.inv(); rep(i,0,n)g[i]=(*this)[i+k]*ic; g=g.log(); for(auto& x:g)x*=t; g=g.exp(); c=c.pow(t); rep(i,0,n)res[i+t*k]=g[i]*c; return res; } void NTT(vector& a,bool inv)const; }; /** * @brief Formal Power Series (NTT-friendly mod) */ #line 7 "sol.cpp" using Fp=fp<998244353>; NTT ntt; template<>void Poly::NTT(vector& v,bool inv)const{return ntt.ntt(v,inv);} #line 2 "library/FPS/prodofpolys.hpp" templatePoly ProdOfPolys(vector>& fs){ if(fs.empty())return Poly({T(1)}); sort(ALL(fs),[&](Poly& a,Poly& b){return a.size()> deq; for(auto& f:fs)deq.push_back(f); while(deq.size()>1){ deq.push_back(deq[0]*deq[1]); deq.pop_front(); deq.pop_front(); } return deq[0]; } /** * @brief Product of Polynomials */ #line 12 "sol.cpp" templatevector EnumSumOfPower(vector& a,int m){//1<=i<=m,sum_k a_k^i int n=a.size(); vector> fs(n); rep(i,0,n)fs[i]=Poly({T(1),T(-a[i])}); auto ret=ProdOfPolys(fs); ret.resize(m+1); return -ret.log().diff(); } FastIO io; int main(){ int n,m; io.read(n,m); vector a(n); rep(i,0,n)io.read(a[i].v); auto ret=EnumSumOfPower(a,m); vector _; for(auto& x:ret)_.push_back(x.v); io.write(_); return 0; }