题目描述

$N$ 頂点の木があり、各頂点には $1$ から $N$ までの番号が振られています。また、$i$ 本目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでいます。

この木の持ち主であるあなたは、いくつかの頂点 ($0$ 個でもよい) を選んで高橋くんを配置し、木の警備をさせることにしました。頂点 $x$ に配置された高橋くんは、$x$ と直接辺で結ばれた頂点、及び $x$ 自身を警備します。

高橋くんを配置する頂点の選び方は $2^N$ 通りありますが、そのうち $1$ 人以上の高橋くんに警備された頂点の個数がちょうど $K$ 個となるような選び方はいくつありますか？

$K=0,1,\ldots,N$ について答えを求め、$(10^9+7)$ で割ったあまりを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ とした場合の答えを出力すること。

题目大意

给出一棵有 $n$ 个节点的树，每个点可能有一个警卫，每个警卫控制当前节点以及相邻节点。

对每个 $k=0,1,2,\cdots n$ 求出正好有 $k$ 个节点被控制的方案数。

$n\le 2000$

3
1 3
1 2

1
0
2
5

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\ \leq\ N\ \leq\ 2000$
• $1\ \leq\ u_i\ \lt\ v_i\ \leq\ N$
• 与えられるグラフは木
• 入力は全て整数

Sample Explanation 1

高橋くんを配置する頂点の選び方は、以下の $8$ 通りです。 - どの頂点にも高橋くんを配置しない。いずれの頂点も高橋くんに警備されていない状態となる。 - 頂点 $1$ に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。 - 頂点 $2$ に高橋くんを配置する。頂点 $1$, $2$ の $2$ つが高橋くんに警備された状態となる。 - 頂点 $3$ に高橋くんを配置する。頂点 $1$, $3$ の $2$ つが高橋くんに警備された状態となる。 - 頂点 $1$ と頂点 $2$ に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。 - 頂点 $1$ と頂点 $3$ に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。 - 頂点 $2$ と頂点 $3$ に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。 - 全ての頂点に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。