Farmer John のサーカスの $N$ 頭の牛（$1 \leq N \leq 10^5$）は、次の演目を準備しています。すべての演目は、頂点に $1\ldots N$ の番号が付けられた木の上で行われます。演目の「初期状態」は、数 $1 \leq K \leq N$ と、牛 $1\dots K$ を木の頂点に配置したもので定義され、どの 2 頭の牛も同じ頂点にいないものとします。

演目では、牛たちは任意に多くの「移動」を行います。1 回の移動では、1 頭の牛が現在の頂点から、牛のいない隣接頂点に移動します。一連の移動によって一方から他方に到達できるとき、2 つの初期状態は同値であるといいます。

各 $1 \leq K \leq N$ について、初期状態の同値類の数を求めるのを手伝ってください。つまり、どの 2 つも同値でないように選べる初期状態の最大数を求めます。これらの数は非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

$1$ 行目に $N$ が与えられます。

各 $2\le i\le N$ 行目には、木の中の $a_i$ と $b_i$ を結ぶ辺を表す 2 つの整数 $a_i$ と $b_i$ が与えられます。

出力

各 $1\le i\le N,$ について、出力の $i$ 行目には $K=i$ に対する答えを $10^9+7$ で割った余りを出力してください。

入出力例

入力 1

5
1 2
2 3
3 4
3 5

出力 1

1
1
3
24
120

注記

$K=1$ と $K=2,$ のとき、任意の 2 つの状態は互いに変換できます。

次に $K=3$ を考え、$c_i$ を牛 $i$ の位置とします。状態 $(c_1,c_2,c_3)=(1,2,3)$ は状態 $(1,2,5)$ および $(1,3,2).$ と同値です。しかし、状態 $(2,1,3).$ とは同値ではありません。

入力 2

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

出力 2

1
1
1
6
30
180
5040
40320

小課題

• テストケース 3–4 は $N\le 8.$ を満たします。
• テストケース 5–7 は $N\le 16.$ を満たします。
• テストケース 8–10 は $N\le 100$ を満たし、木は「星型」です。次数が 2 より大きい頂点は高々 1 つです。
• テストケース 11–15 は $N\le 100$ を満たします。
• テストケース 16–20 に追加の制約はありません。

問題作成者：Dhruv Rohatgi