题目背景

本题满分 $110$。

题目描述

在遥远的 Airlanvaosma-i 国度，有 $n$ 座城市，由 $n-1$ 条道路连接，且从任意城市到任意城市都能到达。并且任意两座城市之间的最短路经过的道路数都小于 $36$。

Krešimir 想建立自己的国家。一个国家必须选择：

• $1$ 个首都（从这里治理国家）；
• 若干个（可以为 $0$ 个）次级城市（归首都管辖）。

国家的规模定义为该国家包含的城市总数（包含首都和所有次级城市）。

为了保证治理效率，Krešimir 规定：

• 对每一个次级城市，在从首都到该次级城市的路径上，不能出现其他次级城市。
  换句话说：不允许某个次级城市位于首都与另一个次级城市之间。

对每个规模 $k$（$1 \le k \le n$），求 Krešimir 能建立多少个不同规模为 $k$ 的国家。答案可能很大，请输出它对 $10^9+7$ 取模的结果。

定义两个国家建立方案不同，当且仅当两个国家在“首都选择”或“任一被选为次级城市的城市”上有不同。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 3000$），表示城市数量。

接下来 $n-1$ 行，每行包含两个整数 $u, v$（$1 \le u, v \le n$，$u \ne v$），表示城市 $u$ 与 $v$ 之间有道路。

输出格式

输出一行包含 $n$ 个整数，分别表示规模为 $1,2,\dots,n$ 的国家数量对 $10^9+7$ 取模的值。

4
1 2
1 3
1 4

4 12 6 1

4
1 2
2 3
1 4

4 12 4 0

提示

【样例解释】

样例 #2 解释：

• 规模为 $1$：只有选首都，因此共 $4$ 种方案。
• 规模为 $2$：先选首都（$4$ 种），再选 $1$ 个次级城市（剩下 $3$ 种），因此共 $12$ 种方案。
• 规模为 $3$：当首都选 $1$ 或 $2$ 时，各有 $2$ 种方案选择 $2$ 个次级城市，因此共 $4$ 种方案。

【子任务】

子任务	分值	限制
$1$	$18$	$1 \le n \le 15$
$2$	$17$	$1 \le n \le 200$
$3$	$26$	$1 \le n \le 600$
$4$	$49$	无额外限制