F - Tree Patrolling

Score : $600$ points

Problem Statement

You have a tree with $N$ vertices, numbered $1$ through $N$. The $i$-th edge connects Vertex $u_i$ and Vertex $v_i$.

You will choose some vertices (possibly none) and place a takahashi in each of them to guard the tree. A takahashi placed at Vertex $x$ will guard $x$ itself and the vertices directly connected to $x$ by an edge.

There are $2^N$ ways to choose vertices for placing takahashi. In how many of them will there be exactly $K$ vertices guarded by one or more takahashi?

Find this count and print it modulo $(10^9+7)$ for each $K=0,1,\ldots,N$.

Constraints

• $1 \leq N \leq 2000$
• $1 \leq u_i \lt v_i \leq N$
• The given graph is a tree.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\hspace{0.6cm}\vdots$

$u_{N-1}$ $v_{N-1}$

Output

Print $N+1$ lines. The $i$-th line should contain the answer for $K=i-1$.

3
1 3
1 2

1
0
2
5

There are eight ways to choose vertices for placing takahashi, as follows:

• Place a takahashi at no vertices, guarding no vertices.
• Place a takahashi at Vertex $1$, guarding all vertices.
• Place a takahashi at Vertex $2$, guarding Vertices $1$ and $2$.
• Place a takahashi at Vertex $3$, guarding Vertices $1$ and $3$.
• Place a takahashi at Vertices $1$ and $2$, guarding all vertices.
• Place a takahashi at Vertices $1$ and $3$, guarding all vertices.
• Place a takahashi at Vertices $2$ and $3$, guarding all vertices.
• Place a takahashi at all vertices, guarding all vertices.

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