P3711 Hamster's Math Problem

Please note that the time limit is 1 s and O2 optimization is enabled. You may need fast I/O.

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.

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

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$.

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