重心概率

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

考虑顶点编号为 $1,2,\ldots,n$ 的所有树。$n$ 是奇数，并且这些树还满足：对于每个 $2\le i\le n$，顶点 $i$ 恰好与一个编号小于 $i$ 的顶点相邻。

对于每个 $1\le i\le n$，求有多少棵满足上述条件的树以顶点 $i$ 为重心。答案对 $998244353$ 取模。

若删除一个顶点后得到的每个连通块大小都不超过 $(n-1)/2$，则称这个顶点是树的 重心。

输入格式

输入一行一个奇数 $n$。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示顶点 $i$ 成为重心的树的数量，对 $998244353$ 取模。相邻整数之间用一个空格分隔。

样例输入 1

3

样例输出 1

1 1 0

样例输入 2

5

样例输出 2

10 10 4 0 0

样例输入 3

7

样例输出 3

276 276 132 36 0 0 0

样例解释

当 $n=3$ 时共有两棵满足条件的树。边集为 $\{(1,2),(1,3)\}$ 的树以顶点 $1$ 为重心，边集为 $\{(1,2),(2,3)\}$ 的树以顶点 $2$ 为重心。

数据范围

对于所有数据：

• $3\le n<200000$；
• $n$ 为奇数。