Problem Background

Fairy tales are beautiful because they are true but never continued.

Problem Description

Lingluo has recently learned about the prefix sum algorithm. 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 this program times out when $n$ is large. Please help her write a program to calculate $\text{ans}_1, \text{ans}_2, \cdots, \text{ans}_n$. Since the answer values are too large, you only need to tell her the remainder of each number divided by $998244353$.

Input Format

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

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

Output Format

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

Sample Input and Output

Sample Input #1

2 1
1 2 0

Sample Output #1

3 7

Sample Input #2

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

Sample Output #2

59 1687 55618 1937320 69557006 549579657 621247830 250099579 483510144 968467040

Notes

Data Range:

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

Special Property A: The number of $i$ such that $f_i \neq 0$ is at most 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 = \binom{i+2}{2} = \frac{(i+2)(i+1)}{2}$.

见题面 Input 部分

见题面 Output 部分