D - BFS-ordered Tree Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 1400 点

問題文

整数 N が与えられます． 以下の条件を満たす根付き木 T を，BFS-ordered 木と呼ぶことにします．

  • T は 1 から N までの番号がついた N 頂点からなる根付き木である．
  • 根は頂点 1 である．
  • 各頂点 i (2 \leq i \leq N) の親を頂点 p_i とするとき，p_2 \leq p_3 \leq \cdots \leq p_N が成立する．

各 d=1,2,\ldots,(N-1) に対し，以下の条件を満たす BFS-ordered 木 T の個数を 998244353 で割ったあまりを求めてください．

  • T において，頂点 (N-1) と頂点 N の距離がちょうど 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

Score : 1400 points

Problem Statement

You are given an integer N. We call a rooted tree T satisfying the following conditions a BFS-ordered tree.

  • T is a rooted tree with N vertices numbered from 1 to N.
  • The root is vertex 1.
  • Let vertex p_i be the parent of each vertex i (2 \leq i \leq N). Then, p_2 \leq p_3 \leq \cdots \leq p_N holds.

For each d=1,2,\ldots,(N-1), find the number, modulo 998244353, of BFS-ordered trees T satisfying the following condition.

  • The distance between vertices (N-1) and N in T is exactly d. More precisely, when considering T as an undirected tree and the path connecting vertices (N-1) and N, the number of edges in that path is exactly d.

Constraints

  • 2 \leq N \leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N

Output

Output N-1 lines. The i-th line should contain the answer for d=i.

Sample Input 1

2

Sample Output 1

1

Sample Input 2

3

Sample Output 2

1
1

Sample Input 3

4

Sample Output 3

2
2
1

Sample Input 4

5

Sample Output 4

5
5
3
1

Sample Input 5

20

Sample Output 5

477638700
477638700
178405156
178405139
109639972
108787985
86366256
69212603
43976909
22930595
9698374
3355343
947052
215710
38814
5324
524
33
1