P6277 [USACO20OPEN] Circus P

Farmer John 马戏团中的 $N$ 头奶牛正在为即将到来的演出做准备。演出全部在一棵节点编号为 $1\ldots N$ 的树上举行。演出的“初始状态”被定义为一个整数 $K$（$1\leq K\leq N$）使得奶牛 $1\ldots K$ 分布在树上的节点上，并且没有任何两头牛位于相同的节点。 在一场演出中，奶牛们可以“移动”任意次数。在一次“移动”中，一头奶牛可以从自己当前所处的节点移动到一个未被占据的相邻节点。如果一个状态可以通过一系列移动到达另一个状态，我们就称这两个初始状态是等价的。 对于每一个 $1\leq K\leq N$，你需要帮助奶牛确定有多少类等价的初始状态。即选出最多的起始状态数目，使得它们两两不等价。由于数字可能很大，所以只需输出答案 $\bmod \ 10^9+7$ 的结果。

无

无

#### 样例 $1$ 解释： 对于 $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)$。 ----- 对于 $100\%$ 的数据，保证 $1 \le N \le 10^5$。 共 $20$ 个测试点，其中 $1\sim 2$ 为样例，其余性质如下： 对于测试点 $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