Farmer John 的马戏团有 $N$ 头奶牛（$1 \leq N \leq 10^5$），它们正在准备即将到来的表演。表演在一棵顶点编号为 $1 \ldots N$ 的树上进行。表演的“初始状态”由一个数字 $1 \leq K \leq N$ 以及将 $1 \dots K$ 号奶牛分配到树上各顶点的方式定义，要求没有两头奶牛位于同一个顶点。

在表演中，奶牛可以进行任意多次“移动”。在一次移动中，单头奶牛可以从她当前所在的顶点移动到相邻的未被占用的顶点。如果两个初始状态可以通过一系列移动相互到达，则称它们是等价的。

对于每个 $1 \leq K \leq N$，请帮助奶牛确定初始状态的等价类数量：即它们能选择的最大初始状态数，使得其中任意两个状态都不等价。由于这些数字可能非常大，请输出它们对 $10^9 + 7$ 取模后的结果。

输入格式

第 $1$ 行包含 $N$。

第 $2$ 行到第 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示树中 $a_i$ 和 $b_i$ 之间的一条边。

输出格式

对于每个 $1 \leq i \leq 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$，任意两个状态都可以相互转换。

现在考虑 $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 \leq 8$。
• 测试点 5-7 满足 $N \leq 16$。
• 测试点 8-10 满足 $N \leq 100$ 且树为“星形”；至多有一个顶点的度数大于 2。
• 测试点 11-15 满足 $N \leq 100$。
• 测试点 16-20 无额外限制。

题目来源：Dhruv Rohatgi