Home

Contest: Task: Related: TaskE TaskG

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$.

Sample Input 1

3
1 3
1 2

Sample Output 1

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.

Sample Input 2

5
1 3
4 5
1 5
2 3

Sample Output 2

1
0
2
5
7
17

Sample Input 3

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

Sample Output 3

1
0
3
8
15
32
68
110
196
266
325