Description

Given a positive integer $n$, for $s=0,1,\dots,n$, count the number of labeled forests consisting of labeled rooted trees on $n$ nodes such that there exist exactly $s$ binary trees.
Take the result modulo $998244353$.

A binary tree is defined as a labeled rooted tree where each node has at most $2$ children.
Two forests are considered different if and only if there exists a node whose parent is different (treat the root as having no parent).

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 9 6 1

4

4 60 48 12 1

5

85 560 480 150 20 1

Hint

[Explanation for Sample 1]

With $3$ nodes, only binary trees can appear, so the number of valid configurations for $s=0$ is $0$.
There are $9$ labeled rooted binary trees on $3$ nodes, so the number of valid configurations for $s=1$ is $9$.
There are $2$ labeled rooted binary trees on $2$ nodes, so the number of valid configurations for $s=2$ is $3 \times 2 = 6$.
A single node is also considered a labeled rooted binary tree, so the number of valid configurations for $s=3$ is $1$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (5 points): $n \le 5$.
• Subtask 2 (5 points): $n \le 10$.
• Subtask 3 (30 points): $n \le 10^3$.
• Subtask 4 (30 points): $n \le 8 \times 10^3$.
• Subtask 5 (30 points): no special constraints.

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$。

Translated by ChatGPT 5