配点 : $600$ 点

問題文

$1$ から $N$ までの番号が付けられた $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$ に対する問題の答えを、順番に一行に出力せよ。

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

この入力中のグラフは以下のようなものです。