[Usaco2020 Open]Circus

内存限制：512 MiB 时间限制：3 Sec

Farmer John 马戏团的 N 头奶牛（1≤N≤10^5）正在准备她们接下来的演出。演出在一棵结点编号为 1…N 的树上进行。演出的“起始状态”可以定义为一个整数 1≤K≤N 以及奶牛 1…K 在树上的结点分布，使得没有两头奶牛位于相同的结点。

在一场演出中，奶牛们可以进行任意次数的“移动”。在一次移动中，一头奶牛从她的当前所在结点移动到一个未被占据的相邻结点。称两个起始状态是等价的，如果一个状态可以通过一系列移动到达另一个。

对于每一个 1≤K≤N，帮助奶牛们求出起始状态的等价类数量：即可选出的起始状态的最大数量，使得两两不等价。由于这些数字可能很大，输出模 10^9+7 的余数。

输入的第 1 行包含 N。

第 2≤i≤N 行每行包含两个整数 ai 和 bi，表示树上连接 ai 和 bi 的一条边。

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


			1

1

3

24

120

对于 K=1 和 K=2，任意两个状态之间都可以相互到达。

考虑 K=3，令 ci 为奶牛 i 的位置。状态 (c1,c2,c3)=(1,2,3) 等价于状态 (1,2,5) 和 (1,3,2)，然而不等价于状态 (2,1,3)。

#5565. [Usaco2020 Open]Circus