树的巡逻

题目描述

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

你将选择一些顶点（可以一个都不选），并在每个被选的顶点上放置一个高桥君来守卫这棵树。放在顶点 $x$ 的高桥君会守卫 $x$ 本身以及与 $x$ 直接相连的所有顶点。

选择放置高桥君的顶点共有 $2^N$ 种方式。其中有多少种方式恰好有 $K$ 个顶点被至少一个高桥君守卫？

对每个 $K=0,1,\ldots,N$，输出该数量对 $(10^9+7)$ 取模后的值。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出 $N+1$ 行。第 $i$ 行输出 $K=i-1$ 对应的答案。

样例

3
1 3
1 2

1
0
2
5

选择放置高桥君的顶点共有以下 $8$ 种方式：

• 不放置任何高桥君，不守卫任何顶点。
• 在顶点 $1$ 放置高桥君，守卫所有顶点。
• 在顶点 $2$ 放置高桥君，守卫顶点 $1$ 和 $2$。
• 在顶点 $3$ 放置高桥君，守卫顶点 $1$ 和 $3$。
• 在顶点 $1$ 和 $2$ 放置高桥君，守卫所有顶点。
• 在顶点 $1$ 和 $3$ 放置高桥君，守卫所有顶点。
• 在顶点 $2$ 和 $3$ 放置高桥君，守卫所有顶点。
• 在所有顶点放置高桥君，守卫所有顶点。

5
1 3
4 5
1 5
2 3

1
0
2
5
7
17

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

1
0
3
8
15
32
68
110
196
266
325

数据范围

• $1 \le N \le 2000$
• $1 \le u_i \lt v_i \le N$
• 给定的图是一棵树
• 输入均为整数