QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[+2]

# 1997. Circus

Statistics

The N cows of Farmer John's Circus (1N105) are preparing their upcoming acts. The acts all take place on a tree with vertices labeled 1N. The "starting state" of an act is defined by a number 1KN and an assignment of cows 1K to the vertices of the tree, so that no two cows are located at the same vertex.

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 1KN, 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 109+7.

INPUT FORMAT (file circus.in):

Line 1 contains N.

Lines 2iN each contain two integers ai and bi denoting an edge between ai and bi in the tree.

OUTPUT FORMAT (file circus.out):

For each 1iN, the i-th line of output should contain the answer for K=i modulo 109+7.

SAMPLE INPUT:

5
1 2
2 3
3 4
3 5

SAMPLE OUTPUT:

1
1
3
24
120

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

Now consider K=3, and let ci denote the location of cow i. The state (c1,c2,c3)=(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 N8.
  • Test cases 5-7 satisfy N16.
  • Test cases 8-10 satisfy N100 and the tree forms a "star;" at most one vertex has degree greater than two.
  • Test cases 11-15 satisfy N100.
  • Test cases 16-20 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi