分配整数

题目描述

有一棵具有 $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$,将问题的答案按顺序每行输出一个。

样例

3
1 2
1 3

2
1
1

该输入中的图如下所示。

对于 $k=1$ 的问题,有以下 $2$ 种整数写法:

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

2
1 2

1
1

该输入中的图如下所示。

5
1 2
2 3
3 4
3 5

2
8
12
3
3

该输入中的图如下所示。

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

40
280
840
120
120
504
72
72

该输入中的图如下所示。

数据范围

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