P3789 Azuki loves coloring

After the release of NEKOPARA Vol.3, Azuki, who is not the protagonist in the new work, can finally take a break. To pass the time, she starts coloring a sequence of $n$ cells, each cell being one of three colors: black, white, or gray. For aesthetics, Azuki wants no two black cells to be adjacent and no two white cells to be adjacent. There are many such sequences. Azuki defines the weight of a sequence as the number of occurrences where a black cell and a white cell are adjacent. For example, the weight of the sequence "gray black white black" is $2$. Azuki wants to know, for each $i$ with $0 \le i \le k$, how many sequences of length $n$ have weight $i$. Since the answers can be large, she only needs the values $\text{mod }998244353$. Azuki promises that if you solve this problem, she will make you ~~delicious cake~~.

One line with two positive integers $n, k$.

One line with $k+1$ positive integers, representing the values $\text{mod }998244353$ of the numbers of sequences whose weights are $0, 1, \dots, k$.

For $30\%$ of the testdata, $n, k \le 100$. For $50\%$ of the testdata, $n, k \le 5000$, time limit $1\ \text{s}$. The remaining testdata have time limit $5\ \text{s}$. For $70\%$ of the testdata, $n, k \le 60000$. For $100\%$ of the testdata, $n \le 10^{18}, k \le 100000$. Translated by ChatGPT 5