Filling Cells with Catalan Weights and Colorings

You are given an infinite row of cells numbered from 1,2,3,…. In each cell you may write any positive integer k; in doing so you obtain a weight of \(C_k\) defined by

\(C_0=C_1=1,\quad C_i=\sum_{j=0}^{i-1} C_j\,C_{i-j-1}\quad (i\ge2).\)

The total weight of several cells is defined as the product of the individual cell weights.

You will fill cells from left to right. In each new cell you write a positive integer. You continue filling cells until the sum of the written numbers is at least \(n\). After that, you must stop. (Only sequences whose sum is exactly \(n\) are considered valid.)

Then, you color each filled cell either black or white subject to the following restrictions:

• The first filled cell must be colored black and the last filled cell must be colored white.
• No two or more consecutive filled cells may be white.

Next, for each pair of consecutive filled cells that have the same color, draw an edge between them. (Thus if several adjacent cells share the same color, every adjacent pair is connected by an edge.)

Finally, you choose a subset \(S\) of the filled cells (possibly empty) such that no two cells in \(S\) are connected by an edge; that is, for every drawn edge, at most one of its endpoints belongs to \(S\). Two schemes are considered different if they differ in any of the following: the number of filled cells, the numbers written in the cells, the colors of the cells, or the chosen set \(S\).

The weight of a scheme is defined as the product of the weights of the filled cells (i.e. the product of \(C_k\) for the written numbers). Your task is: for a given \(n\) and for every \(s=0,1,\dots,n\) (where \(s\) is the number of black cells), compute the sum (modulo \(998244353\)) of the weights of all schemes whose written numbers add up exactly to \(n\) and which have exactly \(s\) black cells.

inputFormat

The input consists of a single integer \(n\) on one line.

\(1 \le n \le \text{(small limit)}\)

outputFormat

Output \(n+1\) space‐separated integers. The \(i\)th integer (starting from \(i=0\)) should equal the sum of the weights (modulo \(998244353\)) of all valid schemes with exactly \(i\) black cells.

sample

1

0 0