There is a number $*x*$ initially written on a blackboard. You repeat the following action a fixed amount of times:

1. take the number $*x*$ currently written on a blackboard and erase it
2. select an integer uniformly at random from the range $[0, *x*]$ inclusive, and write it on the blackboard

Determine the distribution of final number given the distribution of initial number and the number of steps.

Input

The first line contains two integers, $*N*$ ($1 ≤ *N* ≤ 10^{5}$) — the maximum number written on the blackboard — and $*M*$ ($0 ≤ *M* ≤ 10^{18}$) — the number of steps to perform.

The second line contains $*N* + 1$ integers $*P*_{0}, *P*_{1}, ..., *P*_{*N*}$ ($0 ≤ *P*_{*i*} < 998244353$), where $*P*_{*i*}$ describes the probability that the starting number is $*i*$. We can express this probability as irreducible fraction $*P* / *Q*$, then . It is guaranteed that the sum of all $*P*_{*i*}$s equals $1$ (modulo $998244353$).

Output

Output a single line of $*N* + 1$ integers, where $*R*_{*i*}$ is the probability that the final number after $*M*$ steps is $*i*$. It can be proven that the probability may always be expressed as an irreducible fraction $*P* / *Q*$. You are asked to output .

Note

In the first case, we start with number 2. After one step, it will be 0, 1 or 2 with probability 1/3 each.

In the second case, the number will remain 2 with probability 1/9. With probability 1/9 it stays 2 in the first round and changes to 1 in the next, and with probability 1/6 changes to 1 in the first round and stays in the second. In all other cases the final integer is 0.