问题描述

#nck { width: 30px; height: auto; }

某天，高桥从青木那里得到了以下问题：

• 给定一棵具有$N$个顶点的树和一个整数$K$。顶点编号为$1$到$N$。边由整数对$(a_i, b_i)$表示。
• 对于树中的一个顶点集合$S$，定义$f(S)$为包含$S$中所有顶点的子树中最小的顶点数。
• 从这棵树中选择$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