Cow Performance Reconfiguration

In Farmer John’s circus, there are (N) cows preparing for a show that takes place on a tree with nodes numbered (1,2,\ldots,N). An initial state for the performance is defined by an integer (K) (with (1\le K\le N)) together with an assignment of cows (1,2,\ldots,K) to (K) distinct nodes of the tree. During the show the cows may move arbitrarily many times. In one move a cow may slide from its current node to an adjacent node provided that the target node is unoccupied. We say that two initial states are equivalent if one can be reached from the other via a series of legal moves.

For each (K) ((1\le K\le N)) the cows would like to know the number of equivalence classes of initial states; that is, what is the maximum number of initial states you can choose so that no two of them are equivalent. Since the answers can be very large, output each answer modulo (10^9+7).

A key observation is that the moves are exactly the swaps of a cow and an adjacent empty vertex (a "blank"). It is known that the sliding puzzle with a single blank on a bipartite graph (such as a tree) has exactly two connected components, while if there are at least two blanks the reconfiguration graph is connected. In our problem the configuration has (N-K) blanks. Hence, for a given (K):

• If (N-K\ge2) (i.e. (K\le N-2)) then all configurations are equivalent (answer = 1).
• If (N-K=1) (i.e. (K=N-1) and (N>1)) then the sliding puzzle invariant on bipartite graphs forces exactly two equivalence classes (answer = 2).
• Finally, if (K=N) then there is only one configuration (answer = 1).

Note that if (N=1) the only possibility is (K=1) and the answer is 1.

inputFormat

The first line contains a single integer \(N\) (\(1\le N\le 10^5\)), the number of nodes in the tree.

Then \(N-1\) lines follow, each containing two integers \(u\) and \(v\) (\(1\le u,v\le N\)) indicating that there is an edge between node \(u\) and node \(v\). The graph is guaranteed to be a tree.

outputFormat

Output \(N\) space‐separated integers, where the \(i\)th integer is the number of equivalence classes for \(K=i\) (modulo \(10^9+7\)).

sample

1

1