题目描述

We have a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge in this tree connects Vertex $a_i$ and $b_i$. For each $k=1, ..., N$, solve the problem below:

• Consider writing a number on each vertex in the tree in the following manner:
  • First, write $1$ on Vertex $k$.
  • Then, for each of the numbers $2, ..., N$ in this order, write the number on the vertex chosen as follows:
    • Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.
• Find the number of ways in which we can write the numbers on the vertices, mod $(10^9+7)$.

我们有一棵树，树上有 $N$ 个顶点，编号为 $1$ 至 $N$ 。树中的第 $i$ 条边连接顶点 $a_i$ 和 $b_i$ 。请针对每一个 $k=1, ..., N$ 解决下面的问题：

• 考虑按以下方式在树的每个顶点上写一个数字：
  • 首先，在顶点 $k$ 上写下 $1$ 。
  • 然后，依次在每个数字 $2, ..., N$ 上写出所选顶点上的数字，如下所示：
    • 选择一个仍未写上数字的顶点，并与已写上数字的顶点相邻。如果有多个这样的顶点，随机选择其中一个。
• 求在顶点上写上数字的方法的数目，模为 $(10^9+7)$ 。

输入格式

输入内容按以下格式标准输入：

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

输出格式

对于顺序中的每一个 $k=1, 2, ..., N$ ，打印一行包含问题答案的内容。

样例 #1

样例输入 #1

3
1 2
1 3

样例输出 #1

2
1
1

样例 #2

样例输入 #2

2
1 2

样例输出 #2

1
1

样例 #3

样例输入 #3

5
1 2
2 3
3 4
3 5

样例输出 #3

2
8
12
3
3

样例 #4

样例输入 #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

说明

数据规模与约定

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

样例 $1$ 解释

该输入的图表如下

对于 $k=1$ ，我们可以用以下两种方法来书写顶点上的数字：

• 分别将 $1, 2, 3$ 写在顶点 $1, 2, 3$ 上
• 分别在顶点 $1, 2, 3$ 上写入 $1, 3, 2$

样例 $2$ 解释

该输入的图形如下

样例 $3$ 解释

该输入的图形如下

样例 $4$ 解释

该输入的图形如下