#line 1 "verify/yosupo/polynomial/formal-power-series/pow_of_formal_power_series.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/pow_of_formal_power_series"
#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;
const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) (int)(a.size())
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define FIND(a,x) (int)(find(ALL(a),x)-a.begin())
#define COUNT(a,x) (int)count(ALL(a),x)
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))
template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}
template<class T>
T floor(T a,T b){return a/b-((a^b)<0&&a%b);}
template<class T>
T ceil(T a,T b){return a/b+((a^b)>=0&&a%b);}
int popcnt(ll x){return __builtin_popcountll(x);}
int topbit(ll x){return x==0?-1:63-__builtin_clzll(x);}
int lowbit(ll x){return x==0?-1:__builtin_ctzll(x);}
template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
template<class T>
vector<int> argsort(const vector<T> &a){
vector<int> p(SZ(a));
iota(ALL(p),0);
stable_sort(ALL(p),[&](int i,int j){return a[i]<a[j];});
return p;
}
template<class T,size_t D=0>
struct VecBuilder{
array<size_t,D> d;
VecBuilder<T,D+1> operator[](size_t n)const{
VecBuilder<T,D+1> res{};
for(size_t i=0;i<D;i++)res.d[i]=d[i];
res.d[D]=n;
return res;
}
template<size_t I=0>
auto build(const T &x)const{
if constexpr(I+1==D)return vector<T>(d[I],x);
else return vector<decltype(build<I+1>(x))>(d[I],build<I+1>(x));
}
auto operator()(const T &x=T())const{
static_assert(D>0);
return build(x);
}
};
template<class T>
inline constexpr VecBuilder<T> VEC{};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "modular-arithmetic/modint.hpp"
/**
* Author: Teetat T.
* Date: 2026-04-15
* Description: modular arithmetic operations
*/
template<int mod,int root=0>
struct ModInt{
using mint = ModInt;
static_assert(mod>0,"mod must be positive");
int x;
constexpr ModInt():x(0){}
constexpr ModInt(ll x):x((x%=mod)<0?x+mod:x){}
constexpr explicit operator int()const{return x;}
constexpr int val()const{return x;}
constexpr static int get_mod(){return mod;}
constexpr static mint get_root(){return mint(root);}
constexpr mint operator-()const{
mint res;
res.x=x?mod-x:0;
return res;
}
constexpr mint operator+()const{return *this;}
constexpr mint inv()const{
int a=x,b=mod,u=1,v=0,q=0;
while(b>0){
q=a/b;
swap(a-=q*b,b);
swap(u-=q*v,v);
}
return mint(u);
}
constexpr mint pow(ll n)const{
mint res=1,a=*this;
for(;n>0;a*=a,n>>=1)if(n&1)res*=a;
return res;
}
constexpr mint &operator+=(const mint &o){
if((x+=o.x)>=mod)x-=mod;
return *this;
}
constexpr mint &operator-=(const mint &o){
if((x-=o.x)<0)x+=mod;
return *this;
}
constexpr mint &operator*=(const mint &o){
x=(ll(x)*o.x)%mod;
return *this;
}
constexpr mint &operator/=(const mint &o){
return *this*=o.inv();
}
constexpr mint operator+(const mint &o)const{return mint(*this)+=o;}
constexpr mint operator-(const mint &o)const{return mint(*this)-=o;}
constexpr mint operator*(const mint &o)const{return mint(*this)*=o;}
constexpr mint operator/(const mint &o)const{return mint(*this)/=o;}
constexpr mint &operator++(){return *this+=mint(1);}
constexpr mint &operator--(){return *this-=mint(1);}
constexpr mint operator++(int){mint res=*this;*this+=mint(1);return res;}
constexpr mint operator--(int){mint res=*this;*this-=mint(1);return res;}
constexpr bool operator==(const mint &o)const{return x==o.x;}
constexpr bool operator!=(const mint &o)const{return x!=o.x;}
constexpr bool operator<(const mint &o)const{return x<o.x;}
friend istream &operator>>(istream &is,mint &o){ll x{};is>>x;o=mint(x);return is;}
friend ostream &operator<<(ostream &os,const mint &o){return os<<o.x;}
};
using mint998 = ModInt<998244353,3>;
using mint107 = ModInt<1000000007>;
#line 2 "modular-arithmetic/binpow.hpp"
/**
* Author: Teetat T.
* Date: 2024-01-15
* Description: n-th power using divide and conquer
* Time: $O(\log b)$
*/
template<class T>
constexpr T binpow(T a,ll b){
T res=1;
for(;b>0;b>>=1,a*=a)if(b&1)res*=a;
return res;
}
#line 3 "polynomial/ntt.hpp"
/**
* Author: Teetat T.
* Description: Number Theoretic Transform
* Time: $O(N \log N)$
*/
template<class mint>
struct NTT{
using vm = vector<mint>;
static constexpr ll mod=mint::get_mod();
static constexpr mint root=mint::get_root();
static_assert(root!=0, "root must be nonzero");
static void ntt(vm &a){
int n=a.size(),L=31-__builtin_clz(n);
vm rt(n);
rt[1]=1;
for(int k=2,s=2;k<n;k*=2,s++){
mint z[]={1,binpow(root,mod>>s)};
for(int i=k;i<2*k;i++)rt[i]=rt[i/2]*z[i&1];
}
vector<int> rev(n);
for(int i=1;i<n;i++)rev[i]=(rev[i/2]|(i&1)<<L)/2;
for(int i=1;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int k=1;k<n;k*=2)for(int i=0;i<n;i+=2*k)for(int j=0;j<k;j++){
mint z=rt[j+k]*a[i+j+k];
a[i+j+k]=a[i+j]-z;
a[i+j]+=z;
}
}
static vm conv(const vm &a,const vm &b){
if(a.empty()||b.empty())return {};
int s=a.size()+b.size()-1,n=1<<(32-__builtin_clz(s));
mint inv=mint(n).inv();
vm in1(a),in2(b),out(n);
in1.resize(n),in2.resize(n);
ntt(in1),ntt(in2);
for(int i=0;i<n;i++)out[-i&(n-1)]=in1[i]*in2[i]*inv;
ntt(out);
return vm(out.begin(),out.begin()+s);
}
vm operator()(const vm &a,const vm &b){
return conv(a,b);
}
};
#line 3 "polynomial/formal-power-series.hpp"
/**
* Author: Teetat T.
* Date: 2024-03-17
* Description: basic operations of formal power series
*/
template<class mint>
struct FormalPowerSeries:vector<mint>{
using vector<mint>::vector;
using FPS = FormalPowerSeries;
FPS &operator+=(const FPS &rhs){
if(rhs.size()>this->size())this->resize(rhs.size());
for(int i=0;i<rhs.size();i++)(*this)[i]+=rhs[i];
return *this;
}
FPS &operator+=(const mint &rhs){
if(this->empty())this->resize(1);
(*this)[0]+=rhs;
return *this;
}
FPS &operator-=(const FPS &rhs){
if(rhs.size()>this->size())this->resize(rhs.size());
for(int i=0;i<rhs.size();i++)(*this)[i]-=rhs[i];
return *this;
}
FPS &operator-=(const mint &rhs){
if(this->empty())this->resize(1);
(*this)[0]-=rhs;
return *this;
}
FPS &operator*=(const FPS &rhs){
auto res=NTT<mint>()(*this,rhs);
return *this=FPS(res.begin(),res.end());
}
FPS &operator*=(const mint &rhs){
for(auto &a:*this)a*=rhs;
return *this;
}
friend FPS operator+(FPS lhs,const FPS &rhs){return lhs+=rhs;}
friend FPS operator+(FPS lhs,const mint &rhs){return lhs+=rhs;}
friend FPS operator+(const mint &lhs,FPS &rhs){return rhs+=lhs;}
friend FPS operator-(FPS lhs,const FPS &rhs){return lhs-=rhs;}
friend FPS operator-(FPS lhs,const mint &rhs){return lhs-=rhs;}
friend FPS operator-(const mint &lhs,FPS rhs){return -(rhs-lhs);}
friend FPS operator*(FPS lhs,const FPS &rhs){return lhs*=rhs;}
friend FPS operator*(FPS lhs,const mint &rhs){return lhs*=rhs;}
friend FPS operator*(const mint &lhs,FPS rhs){return rhs*=lhs;}
FPS operator-(){return (*this)*-1;}
FPS rev(){
FPS res(*this);
reverse(res.beign(),res.end());
return res;
}
FPS pre(int sz){
FPS res(this->begin(),this->begin()+min((int)this->size(),sz));
if(res.size()<sz)res.resize(sz);
return res;
}
FPS shrink(){
FPS res(*this);
while(!res.empty()&&res.back()==mint{})res.pop_back();
return res;
}
FPS operator>>(int sz){
if(this->size()<=sz)return {};
FPS res(*this);
res.erase(res.begin(),res.begin()+sz);
return res;
}
FPS operator<<(int sz){
FPS res(*this);
res.insert(res.begin(),sz,mint{});
return res;
}
FPS diff(){
const int n=this->size();
FPS res(max(0,n-1));
for(int i=1;i<n;i++)res[i-1]=(*this)[i]*mint(i);
return res;
}
FPS integral(){
const int n=this->size();
FPS res(n+1);
res[0]=0;
if(n>0)res[1]=1;
ll mod=mint::get_mod();
for(int i=2;i<=n;i++)res[i]=(-res[mod%i])*(mod/i);
for(int i=0;i<n;i++)res[i+1]*=(*this)[i];
return res;
}
mint eval(const mint &x){
mint res=0,w=1;
for(auto &a:*this)res+=a*w,w*=x;
return res;
}
FPS inv(int deg=-1){
assert(!this->empty()&&(*this)[0]!=mint(0));
if(deg==-1)deg=this->size();
FPS res{mint(1)/(*this)[0]};
for(int i=2;i>>1<deg;i<<=1){
res=(res*(mint(2)-res*pre(i))).pre(i);
}
return res.pre(deg);
}
FPS log(int deg=-1){
assert(!this->empty()&&(*this)[0]==mint(1));
if(deg==-1)deg=this->size();
return (pre(deg).diff()*inv(deg)).pre(deg-1).integral();
}
FPS exp(int deg=-1){
assert(this->empty()||(*this)[0]==mint(0));
if(deg==-1)deg=this->size();
FPS res{mint(1)};
for(int i=2;i>>1<deg;i<<=1){
res=(res*(pre(i)-res.log(i)+mint(1))).pre(i);
}
return res.pre(deg);
}
FPS pow(ll k,int deg=-1){
const int n=this->size();
if(deg==-1)deg=n;
if(k==0){
FPS res(deg);
if(deg)res[0]=mint(1);
return res;
}
for(int i=0;i<n;i++){
if(__int128_t(i)*k>=deg)return FPS(deg,mint(0));
if((*this)[i]==mint(0))continue;
mint rev=mint(1)/(*this)[i];
FPS res=(((*this*rev)>>i).log(deg)*k).exp(deg);
res=((res*binpow((*this)[i],k))<<(i*k)).pre(deg);
return res;
}
return FPS(deg,mint(0));
}
};
#line 5 "verify/yosupo/polynomial/formal-power-series/pow_of_formal_power_series.test.cpp"
using mint = mint998;
using FPS = FormalPowerSeries<mint>;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n;
ll m;
cin >> n >> m;
FPS a(n);
for(auto &x:a)cin >> x;
a=a.pow(m);
for(auto x:a)cout << x << " ";
cout << "\n";
}
verify/yosupo/polynomial/formal-power-series/pow_of_formal_power_series.test.cpp