[ABC207F] Tree Patrolling

给出一棵有 $n$ 个节点的树，每个点可能有一个警卫，每个警卫控制当前节点以及相邻节点。 对每个 $k=0,1,2,\cdots n$ 求出正好有 $k$ 个节点被控制的方案数。 $n\le 2000$

[problemUrl]: https://atcoder.jp/contests/abc207/tasks/abc207_f $ 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 $ とした場合の答えを出力すること。

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 $ に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。 - 全ての頂点に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。