Description

Given $n$, take the integer points on the number line in $[1,n]$.

Define a maximal consecutive black segment as an interval $[L,R]$ with $1 \le L \le R \le p$, such that all intervals with indices in $[L,R]$ are black, and it cannot be extended further; that is, the intervals with indices $L-1$ (if it exists; same below) and $R+1$ are both white.

First, you need to partition them into several intervals $[l_1,r_1],[l_2,r_2],\dots,[l_p,r_p]$, satisfying $l_1 = 1$, $r_p = n$, and for $1 \le i < p$ we have $r_i = l_{i+1}-1$; for $1 \le i \le p$ we have $l_i \le r_i$.

Second, you need to mark each interval as black or white, but it is not allowed that both the first interval and the $p$-th interval are marked black at the same time.

Third, within each interval, select a subinterval, called a wonderful subinterval.

Fourth, in each maximal consecutive black segment, select one black interval, called a wonderful black interval.

Fifth, among all maximal consecutive black segments, designate some of them as wonderful maximal consecutive black segments.

Define the weight of a plan determined by the above steps as the sum of the number of black intervals and the number of wonderful maximal consecutive black segments.

Originally, I hoped you would compute, for $s = 0,1,2,\dots,n$, the number of plans that make the final weight equal to $s$. However, I have also prepared some easier challenges. See the input format for details.

The answer should be taken modulo $998244353$.

Input Format

One line with two integers $n,{\rm type}$.

If ${\rm type} = 0$, you need to compute, for $0 \le s \le n$, the number of plans with weight $s$.
If ${\rm type} = 1$, you need to compute the total number of plans over all $0 \le s \le n$.

Output Format

If ${\rm type} = 0$, output one line with $n+1$ non-negative integers, in order, representing the answers for $s = 0,1,2,\dots,n$.
If ${\rm type} = 1$, output one line with one non-negative integer, representing the answer.

3 0

6 13 17 4

5 1

1035

Hint

Sample Explanation

Below, $0$ denotes black and $1$ denotes white.

For the first sample, consider the $4$ partitions of $[1,3]$:

• $[1,1],[2,2],[3,3]$:
  At this time, the number of ways to choose an unordered pair is $1$.
  Considering the black/white marking of each interval, there are the following $4$ plans:
  • $001,100$: in this case, you may choose whether to mark the only maximal consecutive black segment as wonderful or not, so the weight is $2$ or $3$. The number of ways to choose the wonderful black interval is $2$.
  • $101$: in this case, you may choose whether to mark the only maximal consecutive black segment as wonderful or not, so the weight is $1$ or $2$. The number of ways to choose the wonderful black interval is $1$.
• $[1,2],[3,3]$ or $[1,1],[2,3]$:
  At this time, the number of ways to choose an unordered pair is $3$.
  Considering the black/white marking of each interval, there are the following $2$ plans:
  • $01,10$: in this case, you may choose whether to mark the only maximal consecutive black segment as wonderful or not, so the weight is $1$ or $2$. The number of ways to choose the wonderful black interval is $1$.
• $[1,3]$:
  At this time, the number of ways to choose an unordered pair is $6$.
  Considering the black/white marking of each interval, there is the following $1$ plan:
  • $1$: in this case, the weight is $0$, the total number of plans is $6$, and the number of ways to choose the wonderful black interval is $1$. Therefore, the number of plans with weight $0$ is $6 \times 1 = 6$, the number of plans with weight $1$ is $1 \times 1 + 2 \times 3 \times 2 \times 1 = 13$, the number of plans with weight $2$ is $1 \times 2 \times 2 + 1 \times 1 + 2 \times 3 \times 2 \times 1 = 17$, and the number of plans with weight $3$ is $1 \times 2 \times 2 = 4$.

For the second sample, no explanation is provided.

Constraints

This problem uses bundled testdata.

The specific subtask constraints and scores are as follows:

For all testdata, $1 \le n \le 2 \times 10^5$, ${\rm type} \in \{0,1\}$.

Translated by ChatGPT 5