問題文

高橋君はある日青木君から以下の様な問題を貰いました。

• $N$ 頂点の木と、整数 $K$ が与えられる。木の頂点は $1,2,...,N$ と番号がついているものとし、辺は $(a_i, b_i)$ で表す。
• 頂点の集合 $S$ について $f(S)$ を、$S$ をすべて含む部分木の頂点数の最小値とする
• 木から $K$ 個の頂点を選ぶ方法は $_NC_K$ 通りあるが、それぞれについて選んだ頂点を $S$ とし、 $f(S)$ の総和を求める
• 答えは大きくなることがあるので、$924844033$(素数) で割ったあまりを出力する

高橋君にとってこの問題は簡単すぎました。なので $K = 1,2,...,N$ 全てについてこの問題を解くことにしました。

制約

• $2 ≦ N ≦ 200,000$
• $1 ≦ a_i, b_i ≦ N$
• 与えられるグラフは木である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_{N-1}$ $b_{N-1}$

出力

$N$ 行出力する。$i$ 行目には、$K=i$ の時の問題の答えを $924844033$ で割ったあまりを出力する。

入力例 1

3
1 2
2 3

出力例 1

3
7
3

上図は、$K=2$ の場合を図示している。ピンク色の頂点が選んだ頂点で、赤く囲われたのが頂点数最小の部分木である。

入力例 2

4
1 2
1 3
1 4

出力例 2

4
15
13
4

入力例 3

7
1 2
2 3
2 4
4 5
4 6
6 7

出力例 3

7
67
150
179
122
45
7