Problem 3. Circus

USACO 2020 US Open Contest, Platinum

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$ 的余数。

输入格式（文件名：circus.in）：

输入的第 $1$ 行包含 $N$。

第 $2\le i\le N$ 行每行包含两个整数 $a_i$ 和 $b_i$，表示树上连接 $a_i$ 和 $b_i$ 的一条边。

输出格式（文件名：circus.out）：

对于每一个 $1\le i\le N$，在第 $i$ 行输出 $K=i$ 的答案模 $10^9+7$ 的余数。

输入样例：

5
1 2
2 3
3 4
3 5

输出样例：

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)$。

输入样例：

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

输出样例：

1
1
1
6
30
180
5040
40320

测试点性质： 测试点 3-4 满足 $N\le 8$。测试点 5-7 满足 $N\le 16$。测试点 8-10 满足 $N\le 100$ 并且树组成了一个“星形”；至多一个结点的度大于二。测试点 11-15 满足 $N\le 100$。测试点 16-20 没有额外限制。

供题：Dhruv Rohatgi