题目描述

我们有一个包含$N$个顶点的树，顶点编号为$1$到$N$。该树中的第$i$条边连接了顶点$a_i$和$b_i$。对于每个$k=1, ..., N$，解决以下问题：

• 在树的每个顶点上按照以下方式写入一个数字：
  • 首先，在顶点$k$上写入数字$1$。
  • 然后，对于从$2$到$N$的每个数字，按照顺序选择要写入数字的顶点，选择规则如下：
    • 选择一个还没有写入数字的顶点，并且它与已经写入数字的顶点相邻。如果存在多个这样的顶点，则随机选择其中之一。
• 计算我们可以以多少种方式在顶点上写入数字，结果取模$(10^9+7)$。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• 给定的图是一棵树。

输入

从标准输入中以以下格式给出输入：

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

输出

按照顺序为每个$k=1, 2, ..., N$，打印一行，其包含问题的答案。

示例输入1

3
1 2
1 3

示例输出1

2
1
1

该输入中的图如下所示：

对于$k=1$，我们可以以两种方式在顶点上写数字，如下所示：

• 在顶点$1, 2, 3$上依次写入数字$1, 2, 3$
• 在顶点$1, 2, 3$上依次写入数字$1, 3, 2$

示例输入2

2
1 2

示例输出2

1
1

该输入中的图如下所示：

示例输入3

5
1 2
2 3
3 4
3 5

示例输出3

2
8
12
3
3

该输入中的图如下所示：

示例输入4

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

示例输出4

40
280
840
120
120
504
72
72

该输入中的图如下所示：