Description

A hamster saw a problem on some OJ. Let $S_k(x)=\sum_{i=0}^x i^k$. This problem inputs $a_0, a_1 \ldots a_n$. Suppose $0^0=1$. You are asked to compute $\sum_{k=0}^{n} S_k(x) a_k$.

The hamster thought for two seconds and solved it in a flash. He found the constraints were only $1000$, so he casually added two zeros.

But the hamster was too lazy to make testdata, so he threw this problem to you.

Input Format

The first line contains an integer $n$.

The second line contains $n+1$ space-separated non-negative integers: $a_0, \cdots, a_n$.

Output Format

Output $n+2$ space-separated integers, the coefficients $c_0, \cdots, c_{n+1}$ of the answer polynomial, meaning the polynomial is $\sum_{i=0}^{n+1} c_i x^i$. The coefficients are taken modulo $998244353$.

It can be proved that the degree of the polynomial is $\leq n+1$.

2
3 3 3

3 5 3 1

Hint

For $10\%$ of the testdata, $n \leq 500$.

For $30\%$ of the testdata, $n \leq 3000$.

For $70\%$ of the testdata, $n \leq 100000$.

For $100\%$ of the testdata, $1 \leq n \leq 250000$.

Both the input and output polynomial coefficients are taken modulo $998244353$ and are non-negative integers in $[0, 998244352]$.

Translated by ChatGPT 5