Background

A fairy tale is only beautiful in truth, yet it is never continued.

A fairy tale is only beautiful in gentleness, yet it is never continued.

Problem Description

Lingluo has recently been learning the prefix sum algorithm, and she wrote the following program:

read(n),read(a);
for(int i=0;i<=n;i++)read(f[i]);
for(int t=1;t<=n;t++){
    for(int i=1;i<=n;i++)f[i]=f[i]+a*f[i-1];
    ans[t]=f[t];
}

She found that when $n$ is relatively large, this program will time out. Please help write a program to compute $\text{ans}_1,\text{ans}_2,\cdots,\text{ans}_n$. Since the answers are too large, you only need to output each number modulo $998244353$.

Input Format

The first line contains two positive integers $n,a$.

The next line contains $n+1$ non-negative integers, representing $f_0,f_1,\cdots,f_n$.

Output Format

Output $n$ non-negative integers, representing $\text{ans}_1,\text{ans}_2,\cdots,\text{ans}_n$.

2 1
1 2 0

3 7

10 10
5 9 7 8 0 6 3 2 4 10 1

59 1687 55618 1937320 69557006 549579657 621247830 250099579 483510144 968467040

Hint

Constraints:

For $100\%$ of the testdata, it is guaranteed that $2\leqslant n\leqslant 10^6$, $0\leqslant f_i<998244353$, and $1\leqslant a<998244353$.

Special Property A: It is guaranteed that the number of indices $i$ such that $f_i\ne 0$ does not exceed $100$.

Special Property B: It is guaranteed that $a=1$.

Special Property C: It is guaranteed that for all $i\in[0,n]$, $f_i=1$.

Special Property D: It is guaranteed that for all $i\in[0,n]$, $f_i={i+2\choose 2}=\frac{(i+2)(i+1)}{2}$.

Translated by ChatGPT 5