#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
struct mod_int {
int val;
mod_int(long long v = 0) {
if (v < 0)
v = v % MOD + MOD;
if (v >= MOD)
v %= MOD;
val = v;
}
static int mod_inv(int a, int m = MOD) {
// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
int g = m, r = a, x = 0, y = 1;
while (r != 0) {
int q = g / r;
g %= r; swap(g, r);
x -= q * y; swap(x, y);
}
return x < 0 ? x + m : x;
}
explicit operator int() const {
return val;
}
explicit operator uint64_t()const{
return val;
}
mod_int& operator+=(const mod_int &other) {
val += other.val;
if (val >= MOD) val -= MOD;
return *this;
}
mod_int& operator-=(const mod_int &other) {
val -= other.val;
if (val < 0) val += MOD;
return *this;
}
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
return x % m;
/*
// Optimized mod for Codeforces 32-bit machines.
// x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer.
unsigned x_high = x >> 32, x_low = (unsigned) x;
unsigned quot, rem;
asm("divl %4\n"
: "=a" (quot), "=d" (rem)
: "d" (x_high), "a" (x_low), "r" (m));
return rem;*/
}
mod_int& operator*=(const mod_int &other) {
val = fast_mod((uint64_t) val * other.val);
return *this;
}
mod_int& operator/=(const mod_int &other) {
return *this *= other.inv();
}
friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }
friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }
friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }
friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }
mod_int& operator++() {
val = val == MOD - 1 ? 0 : val + 1;
return *this;
}
mod_int& operator--() {
val = val == 0 ? MOD - 1 : val - 1;
return *this;
}
mod_int operator++(int) { mod_int before = *this; ++*this; return before; }
mod_int operator--(int) { mod_int before = *this; --*this; return before; }
mod_int operator-() const {
return val == 0 ? 0 : MOD - val;
}
bool operator==(const mod_int &other) const { return val == other.val; }
bool operator!=(const mod_int &other) const { return val != other.val; }
mod_int inv() const {
return mod_inv(val);
}
mod_int pow(long long p) const {
assert(p >= 0);
mod_int a = *this, result = 1;
while (p > 0) {
if (p & 1)
result *= a;
a *= a;
p >>= 1;
}
return result;
}
friend ostream& operator<<(ostream &stream, const mod_int &m) {
return stream << m.val;
}
};
//#define mod_int MontgomeryModInt32<MOD>
void debug(vector<mod_int> a){
for(auto i:a)cerr<<i<<' ';
cerr<<endl;
}
void r_debug(vector<mod_int> a){
for(auto i:a)cerr<<1/i<<' ';
cerr<<endl;
}
vector<mod_int> inv, factorial, inv_factorial;
void prepare_factorials(int maximum) {
if(maximum+1<inv.size())return;
inv.assign(maximum + 1, 1);
// Make sure MOD is prime, which is necessary for the inverse algorithm below.
for (int p = 2; p * p <= MOD; p++)
assert(MOD % p != 0);
for (int i = 2; i <= maximum; i++)
inv[i] = inv[MOD % i] * (MOD - MOD / i);
factorial.resize(maximum + 1);
inv_factorial.resize(maximum + 1);
factorial[0] = inv_factorial[0] = 1;
for (int i = 1; i <= maximum; i++) {
factorial[i] = i * factorial[i - 1];
inv_factorial[i] = inv[i] * inv_factorial[i - 1];
}
}
inline mod_int C(int n,int m){
assert(n>=m);assert(n<factorial.size());
return factorial[n]*inv_factorial[m]*inv_factorial[n-m];
}
namespace NTT {
vector<mod_int> roots = {0, 1};
vector<int> bit_reverse;
int max_size = -1;
mod_int root;
bool is_power_of_two(int n) {
return (n & (n - 1)) == 0;
}
int round_up_power_two(int n) {
assert(n > 0);
while (n & (n - 1))
n = (n | (n - 1)) + 1;
return n;
}
// Given n (a power of two), finds k such that n == 1 << k.
int get_length(int n) {
assert(is_power_of_two(n));
return __builtin_ctz(n);
}
// Rearranges the indices to be sorted by lowest bit first, then second lowest, etc., rather than highest bit first.
// This makes even-odd div-conquer much easier.
void bit_reorder(int n, vector<mod_int> &values) {
if ((int) bit_reverse.size() != n) {
bit_reverse.assign(n, 0);
int length = get_length(n);
for (int i = 0; i < n; i++)
bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1));
}
for (int i = 0; i < n; i++)
if (i < bit_reverse[i])
swap(values[i], values[bit_reverse[i]]);
}
void find_root() {
int order = MOD - 1;
max_size = 1;
while (order % 2 == 0) {
order /= 2;
max_size *= 2;
}
root = 2;
// Find a max_size-th primitive root of MOD.
while (!((int)root.pow(max_size) == 1 && (int)root.pow(max_size / 2) != 1))
root=root+1;
}
void prepare_roots(int n) {
if (max_size < 0)
find_root();
assert(n <= max_size);
if ((int) roots.size() >= n)
return;
int length = get_length(roots.size());
roots.resize(n);
// The roots array is set up such that for a given power of two n >= 2, roots[n / 2] through roots[n - 1] are
// the first half of the n-th primitive roots of MOD.
while (1 << length < n) {
// z is a 2^(length + 1)-th primitive root of MOD.
mod_int z = root.pow(max_size >> (length + 1));
for (int i = 1 << (length - 1); i < 1 << length; i++) {
roots[2 * i] = roots[i];
roots[2 * i + 1] = roots[i] * z;
}
length++;
}
}
void fft_iterative(int N, vector<mod_int> &values) {
assert(is_power_of_two(N));
prepare_roots(N);
bit_reorder(N, values);
for (int n = 1; n < N; n *= 2)
for (int start = 0; start < N; start += 2 * n)
for (int i = 0; i < n; i++) {
mod_int even = values[start + i];
mod_int odd = values[start + n + i] * roots[n + i];
values[start + n + i] = even - odd;
values[start + i] = even + odd;
}
}
const int FFT_CUTOFF = 150;
vector<mod_int> mod_multiply(vector<mod_int> left, vector<mod_int> right) {
int n = left.size();
int m = right.size();
// Brute force when either n or m is small enough.
if (min(n, m) < FFT_CUTOFF) {
const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) MOD * MOD;
vector<uint64_t> result(n + m - 1);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
result[i + j] += (uint64_t) ((int) left[i]) * ((int) right[j]);
if (result[i + j] > ULL_BOUND)
result[i + j] %= MOD;
}
for (uint64_t &x : result)
if (x >= MOD)
x %= MOD;
return vector<mod_int>(result.begin(), result.end());
}
int N = round_up_power_two(n + m - 1);
left.resize(N);
right.resize(N);
fft_iterative(N, left);
fft_iterative(N, right);
mod_int inv_N = mod_int(N).inv();
for (int i = 0; i < N; i++)
left[i] *= right[i] * inv_N;
reverse(left.begin() + 1, left.end());
fft_iterative(N, left);
left.resize(n + m - 1);
return left;
}
vector<mod_int> sub_conv(vector<mod_int>a,vector<mod_int>b){
int n=b.size();
reverse(b.begin(),b.end());
auto res=mod_multiply(a,b);
return vector<mod_int>(res.begin()+n-1,res.end());
}
vector<mod_int> shift(vector<mod_int> a,mod_int c){
//a(x+c)=\sum x^j 1/j!\sum i!a_i c^{j-i}/(j-i)!
int N=round_up_power_two(a.size());
prepare_factorials(N);
vector<mod_int>tmp(a.size());
mod_int pc=1;
for(int i=0;i<tmp.size();i++,pc*=c){
tmp[i]=pc*inv_factorial[i];
a[i]*=factorial[i];
}
tmp=sub_conv(a,tmp);
for(int i=0;i<a.size();i++){
tmp[i]*=inv_factorial[i];
}
return tmp;
}
vector<mod_int> mod_power(const vector<mod_int> &v, int exponent) {
assert(exponent >= 0);
vector<mod_int> result = {1};
if (exponent == 0)
return result;
for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {
result = mod_multiply(result, result);
if (exponent >> k & 1)
result = mod_multiply(result, v);
}
return result;
}
vector<mod_int> mod_inv(vector<mod_int> a){
int n=a.size();
int N=round_up_power_two(a.size());
a.resize(N*2);
vector<mod_int>res={a[0].inv()};
for(int i=2;i<=N;i<<=1){
vector<mod_int>tmp(a.begin(),a.begin()+i);
int n=(i<<1);
res.resize(n);
tmp.resize(n);
fft_iterative(n,tmp);
fft_iterative(n,res);
mod_int inv_n=mod_int(n).inv();
for(int j=0;j<n;j++)
res[j]=res[j]*(2-tmp[j]*res[j])*inv_n;
reverse(res.begin()+1,res.end());
fft_iterative(n,res);
fill(res.begin()+i,res.end(),0);
}
res.resize(n);
return res;
}
vector<mod_int>integral(vector<mod_int> a){
assert(a.size()<=inv.size());
a.push_back(0);
for(int i=(int)a.size()-1;i>=1;i--){
a[i]=a[i-1]*inv[i];
}
return a;
}
vector<mod_int>differential(vector<mod_int> a){
assert(a.size());
for(int i=0;i<(int)a.size()-1;i++){
a[i]=a[i+1]*(i+1);
}
a.pop_back();
return a;
}
vector<mod_int>ln(vector<mod_int>a){
assert((int)a[0]==1);
auto b=mod_multiply(differential(a),mod_inv(a));
b=integral(b);
b[0]=0;
return b;
}
vector<mod_int>exp(vector<mod_int>a){
int N=round_up_power_two(a.size());
int n=a.size();
a.resize(N*2);
vector<mod_int>res{1};
for(int i=2;i<=N;i<<=1){
auto tmp=res;
tmp.resize(i);
tmp=ln(tmp);
for(int j=0;j<i;j++)tmp[j]=a[j]-tmp[j];
tmp[0]+=1;
res.resize(i);
res=mod_multiply(res,tmp);
fill(res.begin()+i,res.end(),0);
}
res.resize(n);
return res;
}
vector<mod_int> poly_div(vector<mod_int>a,vector<mod_int>b){
if(a.size()<b.size()){
return {0};
}
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
b.resize(a.size()-b.size()+1);
a.resize(b.size());
auto d=mod_multiply(mod_inv(b),a);
d.resize(b.size());
reverse(d.begin(),d.end());
return d;
}
vector<mod_int> poly_mod(vector<mod_int>a,vector<mod_int>b){
auto res=mod_multiply(b,poly_div(a,b));
a.resize(b.size()-1);
res.resize(b.size()-1);
for(int i=0;i<a.size();i++){
a[i]-=res[i];
}
return a;
}
mod_int eval(const vector<mod_int>&f,int x){
mod_int ans;
for(int i=f.size()-1;i>=0;i--)
ans=(ans*x+f[i]);
return ans;
}
vector<mod_int> mod_multiply_all(const vector<vector<mod_int>> &polynomials) {
if (polynomials.empty())
return {1};
struct compare_size {
bool operator()(const vector<mod_int> &x, const vector<mod_int> &y) {
return x.size() > y.size();
}
};
priority_queue<vector<mod_int>, vector<vector<mod_int>>, compare_size> pq(polynomials.begin(), polynomials.end());
while (pq.size() > 1) {
vector<mod_int> a = pq.top(); pq.pop();
vector<mod_int> b = pq.top(); pq.pop();
pq.push(mod_multiply(a, b));
}
return pq.top();
}
mod_int linear_seq(const vector<mod_int>& _init, vector<mod_int> seq,long long n){
//a_n=sum seq_i * a_n-i
reverse(seq.begin(),seq.end());
for(auto& i:seq)i=-i;seq.push_back(1);
vector<mod_int>b=seq;
reverse(b.begin(),b.end());
b=mod_inv(b);
auto poly_mod=[&](vector<mod_int>a){
if(a.size()<seq.size()){
a.resize(seq.size()-1);
return a;
}
vector<mod_int>tmp=a;
reverse(a.begin(),a.end());
b.resize(a.size()-seq.size()+1);
a.resize(b.size());
auto d=mod_multiply(b,a);
d.resize(b.size());
reverse(d.begin(),d.end());
auto res=mod_multiply(seq,d);
tmp.resize(seq.size()-1);
res.resize(seq.size()-1);
for(int i=0;i<tmp.size();i++){
tmp[i]-=res[i];
}
return tmp;
};
vector<mod_int>a{0,1};
vector<mod_int>res{1};
for(;n;n>>=1){
if(n&1){
res=poly_mod(mod_multiply(res,a));
}
a=poly_mod(mod_multiply(a,a));
}
mod_int ans=0;
for(int i=0;i<_init.size();i++){
ans+=_init[i]*res[i];
}
return ans;
}
vector<mod_int> multi_eval(vector<mod_int> F,vector<mod_int> x){
vector<vector<mod_int>>base;
function<void(int,int,int)> build=[&](int l,int r,int o){
if(r-l==1){
base[o]={1,-x[l]};
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1);
build(mid,r,o<<1|1);
base[o]=(mod_multiply(base[o<<1],base[o<<1|1]));
};
vector<mod_int>res(x.size());
int n=max(x.size(),F.size());
x.resize(n);F.resize(n+1);
base.resize(4*n);
build(0,n,1);
function<void(vector<mod_int>,int,int,int)>solve=[&](vector<mod_int> f,int l,int r,int o){
if(r-l==1){
if(l<res.size())res[l]=f[0];
return;
}
int mid=(l+r)>>1;
auto L=sub_conv(f,base[o<<1|1]);
auto R=sub_conv(f,base[o<<1]);
L.resize(mid-l);
R.resize(r-mid);
solve(L,l,mid,o<<1);
solve(R,mid,r,o<<1|1);
};
solve(sub_conv(F,mod_inv(base[1])),0,n,1);
return res;
}
vector<mod_int> multi_inter(const vector<mod_int>& y,const vector<mod_int>& x){
assert(y.size()==x.size());
vector<vector<mod_int>>base;
function<void(int,int,int)> build=[&](int l,int r,int o){
if(r-l==1){
base[o]={-x[l],1};
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1);
build(mid,r,o<<1|1);
base[o]=(mod_multiply(base[o<<1],base[o<<1|1]));
};
int n=x.size();
base.resize(4*n);
int s=clock();
build(0,n,1);
vector<mod_int>pi=differential(base[1]);
vector<mod_int>res=multi_eval(pi,x);
for(int i=0;i<n;i++)res[i]=y[i]/res[i];
function<vector<mod_int>(int,int,int)>solve2=[&](int l,int r,int o){
if(r-l==1){
return vector<mod_int>({res[l]});
}
int mid=(l+r)>>1;
vector<mod_int>L=mod_multiply(solve2(l,mid,o<<1),base[o<<1|1]);
vector<mod_int>R=mod_multiply(solve2(mid,r,o<<1|1),base[o<<1]);
int n=max(L.size(),R.size());
L.resize(n);R.resize(n);
for(int i=0;i<n;i++){
L[i]+=R[i];
}
return L;
};
auto ans=solve2(0,n,1);
ans.resize(n);
return ans;
}
}
vector<mod_int> gen(int n){
vector<mod_int>v;
for(int i=0;i<n;i++)v.push_back(rand()+1);
return v;
}
int main(){
ios::sync_with_stdio(false);
int n,c;
cin>>n>>c;
vector<mod_int>a(n);
for(auto& i:a){
cin>>i.val;
}
for(auto& i:NTT::shift(a,c)){
cout<<i<<' ';
}
}