问题陈述

你有一棵 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

你将选择一些顶点（可能没有）并在每个选中的顶点上放置一个卫兵，来保护这棵树。在顶点 $x$ 上放置一个卫兵将保护 $x$ 本身以及与 $x$ 直接相连的顶点。

共有 $2^N$ 种方式可以选择要放置卫兵的顶点。其中有多少种方式会使得恰好有 $K$ 个顶点被一个或多个卫兵保护？

找到这个数量，并按照 $K=0,1,\\ldots,N$ 的顺序打印出来，对 $(10^9+7)$ 取模。

约束条件

• $1 \\leq N \\leq 2000$
• $1 \\leq u_i \\lt v_i \\leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

输入格式如下，从标准输入中获取：

$N$ $u_1$ $v_1$ $u_2$ $v_2$ $\\hspace{0.6cm}\\vdots$ $u_{N-1}$ $v_{N-1}$

输出

输出 $N+1$ 行。第 $i$ 行应该包含 $K=i-1$ 时的答案。

示例输入 1

3
1 3
1 2

示例输出 1

1
0
2
5

有八种方式可以选择要放置卫兵的顶点，如下所示：

• 不在任何顶点放置卫兵，不保护任何顶点。
• 在顶点 $1$ 放置一个卫兵，保护所有顶点。
• 在顶点 $2$ 放置一个卫兵，保护顶点 $1$ 和顶点 $2$。
• 在顶点 $3$ 放置一个卫兵，保护顶点 $1$ 和顶点 $3$。
• 在顶点 $1$ 和顶点 $2$ 上都放置一个卫兵，保护所有顶点。
• 在顶点 $1$ 和顶点 $3$ 上都放置一个卫兵，保护所有顶点。
• 在顶点 $2$ 和顶点 $3$ 上都放置一个卫兵，保护所有顶点。
• 在所有顶点上都放置一个卫兵，保护所有顶点。

示例输入 2

5
1 3
4 5
1 5
2 3

示例输出 2

1
0
2
5
7
17

示例输入 3

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

示例输出 3

1
0
3
8
15
32
68
110
196
266
325