Counting Brilliant Schemes

Given an integer n, consider the set of integer points on a number line: [1, n]. You have to design a scheme in five steps as follows:

1. Partitioning: Partition the interval [1, n] into contiguous subintervals \([l_1, r_1], [l_2, r_2], \dots, [l_p, r_p]\) satisfying \[ l_1 = 1,\quad r_p = n, \quad r_i = l_{i+1} - 1 \quad (1 \le i < p). \]</p>
2. Coloring: Color each interval either black or white, with the constraint that the first and the last intervals cannot both be black.
3. Choosing Brilliant Subintervals: In each interval, choose a nonempty subinterval (called the brilliant subinterval). (A subinterval of an interval is any contiguous subset of points within it.)
4. Selecting Brilliant Black Intervals: In every maximal contiguous segment of black intervals (i.e. a segment \([L,R]\) such that every interval in that segment is black and it cannot be extended on either side), choose exactly one black interval to mark as the brilliant black interval.
5. Designating Brilliant Maximal Black Segments: Among all maximal contiguous black segments (as defined above), arbitrarily select a subset and call them the brilliant maximal contiguous black segments.

The weight of a scheme is defined as the sum of the total number of black intervals plus the number of brilliant maximal contiguous black segments chosen in step 5.

Your task is: For each \(s = 0, 1, 2, \dots, n\), compute the number of schemes whose weight equals \(s\). Because the answer can be huge, output each count modulo \(998244353\).

Note: The original problem intended to ask for the counts for all \( s \) from 0 up to \( n \). For the purpose of this challenge, the input will be small so that a correct solution can be designed. (You may assume \(n \le 3\) in the test cases.)

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 3\)).

outputFormat

Output \(n+1\) integers separated by spaces. The \(i^{th}\) number (starting from \(i=0\)) represents the number of schemes with weight equal to \(i\), taken modulo \(998244353\).

sample

1

1 0