题目描述

题目译自 USACO 2020 US Open Contest, Platinum Problem 3. Circus

Farmer John 马戏团中的 $N$ 头奶牛正在为即将到来的演出做准备。演出全部在一棵节点编号为 $1\ldots N$ 的树上举行。演出的「初始状态」被定义为一个整数 $K$（$1\leq K\leq N$）使得奶牛 $1\ldots K$ 分布在树上的节点上，并且没有任何两头牛位于相同的节点。

在一场演出中，奶牛们可以「移动」任意次数。在一次「移动」中，一头奶牛可以从自己当前所处的节点移动到一个未被占据的相邻节点。如果一个状态可以通过一系列移动到达另一个状态，我们就称这两个初始状态是等价的。

对于每一个 $1\leq K\leq N$，你需要帮助奶牛确定有多少类等价的初始状态。即选出最多的起始状态数目，使得它们两两不等价。由于数字可能很大，所以只需输出答案 $\bmod 10^9+7$ 的结果。

输入格式

从标准输入中读入数据。

第一行一个整数 $N$。

接下来的 $N-1$ 行，每行两个整数 $a_i,b_i$，表示树中有一条连接 $a_i$ 和 $b_i$ 的边。

输出格式

输出到标准输出中。

输出共 $N$ 行，对于每一个 $1\leq i\leq N$，在第 $i$ 行输出 $K=i$ 时的答案 $\bmod 10^9+7$ 的结果。

5
1 2
2 3
3 4
3 5

1
1
3
24
120

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

1
1
1
6
30
180
5040
40320

数据范围与提示

对于 $100\%$ 的数据，保证 $1 \le N \le 10^5$。

对于测试点 $3 \sim 4$，满足 $N \leq 8$。
对于测试点 $5 \sim 7$，满足 $N \leq 16$。
对于测试点 $8 \sim 10$，满足 $N \leq 100$，且这个树为「星形」，最多有一个度数大于 $2$ 的节点。
对于测试点 $11 \sim 15$，满足 $N \leq 100$。
对于测试点 $16 \sim 20$，无特殊限制。

出题人：Dhruv Rohatgi