Circus

문제

The $NN$ cows of Farmer John's Circus ($1\le N\le {10}^{5}1\; \backslash leq\; N\; \backslash leq\; 10^5$) are preparing their upcoming acts. The acts all take place on a tree with vertices labeled $1\dots N1\backslash ldots\; N$. The "starting state" of an act is defined by a number $1\le K\le N1\; \backslash leq\; K\; \backslash leq\; N$ and an assignment of cows $1\dots K1\backslash dots\; K$ 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 $1\le K\le N1\; \backslash leq\; K\; \backslash 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+710^9\; +\; 7$.

입력

Line $11$ contains $NN$.

Lines $2\le i\le N2\backslash le\; i\backslash le\; N$ each contain two integers $a_{i}a\_i$ and $b_{i}b\_i$ denoting an edge between $a_{i}a\_i$ and $b_{i}b\_i$ in the tree.

출력

For each $1\le i\le N,1\backslash le\; i\backslash le\; N,$ the $ii$-th line of output should contain the answer for $K=iK=i$ modulo ${10}^9+710^9+7$.