在一个名为 Airlanvaosma-i 的遥远国度，有 $n$ 个城市，由 $n - 1$ 条道路连接。从任意一个城市出发，都可以在经过少于 36 条道路的情况下到达其他任何城市。

万能的 Krešimir 想要建立自己的国家。Krešimir 的国家必须包含一个用于管理国家的首都，以及若干个（可以为零个）受其管辖的辅助城市。一个国家的规模等于属于该国家的所有城市总数（即首都和所有辅助城市）。

然而，为了使国家的管理更加高效，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

4
1 2
1 3
1 4

输出样例 1

4 12 6 1

输入样例 2

4
1 2
2 3
1 4

输出样例 2

4 12 4 0

说明

样例 2 解释：

有 4 个大小为 1 的国家，因为首都有 4 种选择。

有 12 个大小为 2 的国家，因为在选择首都（4 种方式）后，我们还需要选择 1 个辅助城市（3 种方式）。

有 4 个大小为 3 的国家，因为如果选择城市 1 或 2 作为首都，我们各有 2 种方式来选择另外 2 个辅助城市。