Description

We have infinitely many cells in a row, numbered from left to right as $1,2,\dots$.

You may fill any positive integer $k$ into each cell, and then you obtain the weight $C_k$.
Here, $C_0=C_1=1$, and $C_i = \sum\limits_{j=0}^{i-1} C_j C_{i-j-1}$ $(i \ge 2)$.
The total weight of several cells is defined as the product of their weights.

Now you need to fill numbers into the cells from left to right, until the sum of the filled numbers becomes equal to $n$ or exceeds $n$.
After that, you need to color each filled cell either black or white, satisfying: there do not exist any $2$ or more consecutive white cells, the first cell must be black, and the last filled cell must be white.
Then, you need to add an edge between every pair of adjacent filled cells that have the same color, and select a set of cells $S$ such that any two cells in $S$ are not connected by an edge (it can be empty).

The weight of a plan is defined as the total weight of all cells.

Given $n$, for $s=0,1,\dots,n$, compute the sum of weights over all plans that complete all operations above, such that the sum of the filled numbers is exactly $n$, and the number of black cells is $s$.
Two plans are different if and only if the number of filled cells is different, or the numbers filled in the corresponding cells are different, or the colors of the corresponding cells are different, or the set $S$ is different.
Take the result modulo $998244353$.

Input Format

The first line contains one positive integer $n$.

Output Format

Output one line with $n+1$ non-negative integers, representing the answers for $s=0,1,\dots,n$.

3

0 16 6 0

8

0 8008 24388 29840 16788 4360 476 16 0

Hint

[Explanation of Sample $1$.]

When $n=3$, there can be $2$ or $3$ cells.
If there are $2$ cells, the filling plans are $[1,2]$ or $[2,1]$, and the total weight is $2 \times C_1 \times C_2 = 4$; the coloring plan is BW, so there must be one black cell; the choices of the set $S$ are $\{\},\{1\},\{2\},\{1,2\}$ (cells are indexed by their numbers).
If there are $3$ cells, the filling plan is $[1,1,1]$, and the weight is $C_1^3=1$; the coloring plan is BBW, so there must be two black cells; the choices of the set $S$ are $\{\},\{1\},\{2\},\{3\},\{1,3\},\{2,3\}$ (cells are indexed by their numbers).
Here, B means black and W means white.

[Constraints.]

This problem uses bundled tests.

• Subtask 1 (30 points): $n\le10$.
• Subtask 2 (20 points): $n\le300$.
• Subtask 3 (20 points): $n \le 5000$.
• Subtask 4 (30 points): no special constraints, time limit is $3.5s$.

For $100\%$ of the testdata, $1 \le n \le 10^5$.

Hint

To make it easier for everyone to get points with brute force, here is the result:

$$C_k = \frac1k \binom{2k}{k-1} = \binom{2k-1}{k-1}-\binom{2k-1}{k-2}$$

Translated by ChatGPT 5