Subtrees

A tree is a connected undirected graph without cycles. A subtree of a tree $T$ is a connected subgraph of $T$.

The number of subtrees depends on the structure of the tree. For example, a path of $n$ vertices has $n(n+1)/2$ subtrees, and a star (one central vertex connected to the other $n-1$ vertices) has $2^{n-1}+n-1$ subtrees.

Similarly, the number of ways to choose two vertex-disjoint subtrees, three vertex-disjoint subtrees, and so on also depends on the structure of the tree.

Regardless of the structure, there are $2n-1$ ways to choose $n-1$ vertex-disjoint subtrees, and exactly one way to choose $n$ vertex-disjoint subtrees (just $n$ isolated vertices).

Given a tree with $n$ vertices, print for each $k$ from 1 to $n$ the number of ways to choose $k$ vertex-disjoint subtrees of the tree.

The first line contains $n$ ($2 \le n \le 100$). The next $n-1$ lines describe the edges of the tree.

Print $n$ integers: for each $k$ from 1 to $n$, the number of ways to choose $k$ vertex-disjoint subtrees of the given tree. Print each number modulo $10^9$.