## USACO 2020 US Open Contest, Platinum

## Problem 3. Circus

Contest has ended.

**Log in to allow submissions in analysis mode**

In an act, the cows make an arbitrarily large number of "moves." In a move, a single cow moves from her current vertex to an unoccupied adjacent vertex. Two starting states are said to be equivalent if one may be reached from the other by some sequence of moves.

For each $1 \leq K \leq N$, help the cows determine the number of equivalence classes of starting states: that is, the maximum number of starting states they can pick such that no two are equivalent. Since these numbers may be very large, output their remainders modulo $10^9 + 7$.

#### INPUT FORMAT (file circus.in):

Line $1$ contains $N$.Lines $2\le i\le N$ each contain two integers $a_i$ and $b_i$ denoting an edge between $a_i$ and $b_i$ in the tree.

#### OUTPUT FORMAT (file circus.out):

For each $1\le i\le N,$ the $i$-th line of output should contain the answer for $K=i$ modulo $10^9+7$.#### SAMPLE INPUT:

5 1 2 2 3 3 4 3 5

#### SAMPLE OUTPUT:

1 1 3 24 120For $K=1$ and $K=2,$ any two states can be transformed into one another.

Now consider $K=3$, and let $c_i$ denote the location of cow $i$. The state $(c_1,c_2,c_3)=(1,2,3)$ is equivalent to the states $(1,2,5)$ and $(1,3,2).$ However, it is not equivalent to the state $(2,1,3).$

#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

1 1 1 6 30 180 5040 40320

#### SCORING:

- Test cases 3-4 satisfy $N\le 8.$
- Test cases 5-7 satisfy $N\le 16.$
- Test cases 8-10 satisfy $N\le 100$ and the tree forms a "star;" at most one vertex has degree greater than two.
- Test cases 11-15 satisfy $N\le 100$.
- Test cases 16-20 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi