分数: 1400 点
问题陈述
给你一个整数 N。 我们称一棵有根的树 T 满足以下条件a BFS 有序树.
- T 是一棵有根树 N 顶点编号自 1 to N.
- 根是顶点 1.
- 让顶点 p_i 是每个顶点的父顶点 i (2 \leq i \leq N)。然后, p_2 \leq p_3 \leq \cdots \leq p_N 成立。
对于每个 d=1,2,\ldots,(N-1),求模数 998244353,BFS 有序树 T 满足以下条件。
- 顶点之间的距离 (N-1) 和 N in T 正是 d。 更准确地说,当考虑 T 作为无向树和连接顶点的路径 (N-1) 和 N,该路径中的边数恰好是 d.
约束
- 2 \leq N \leq 10^6
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
输出
输出 N-1 行。 的 i- 第行应包含以下问题的答案 d=i.
示例输入 1
2
示例输出 1
1
示例输入 2
3
示例输出 2
1 1
示例输入 3
4
示例输出 3
2 2 1
示例输入 4
5
示例输出 4
5 5 3 1
示例输入 5
20
示例输出 5
477638700 477638700 178405156 178405139 109639972 108787985 86366256 69212603 43976909 22930595 9698374 3355343 947052 215710 38814 5324 524 33 1