Description

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.

Input Format

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

Output Format

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

3 3

11 4 2 0

20 10

1398101 4582670 8103780 10126770 9931780 8075094 5618340 3422330 1841460 893790 383524

Hint

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