{"raw_statement":[{"iden":"problem statement","content":"You have a tree with $N$ vertices, numbered $1$ through $N$. The $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$.\nYou will choose some vertices (possibly none) and place a takahashi in each of them to guard the tree. A takahashi placed at Vertex $x$ will guard $x$ itself and the vertices directly connected to $x$ by an edge.\nThere are $2^N$ ways to choose vertices for placing takahashi. In how many of them will there be exactly $K$ vertices guarded by one or more takahashi?\nFind this count and print it modulo $(10^9+7)$ for each $K=0,1,\\ldots,N$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2000$\n*   $1 \\leq u_i \\lt v_i \\leq N$\n*   The given graph is a tree.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\hspace{0.6cm}\\vdots$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"3\n1 3\n1 2"},{"iden":"sample output 1","content":"1\n0\n2\n5\n\nThere are eight ways to choose vertices for placing takahashi, as follows:\n\n*   Place a takahashi at no vertices, guarding no vertices.\n*   Place a takahashi at Vertex $1$, guarding all vertices.\n*   Place a takahashi at Vertex $2$, guarding Vertices $1$ and $2$.\n*   Place a takahashi at Vertex $3$, guarding Vertices $1$ and $3$.\n*   Place a takahashi at Vertices $1$ and $2$, guarding all vertices.\n*   Place a takahashi at Vertices $1$ and $3$, guarding all vertices.\n*   Place a takahashi at Vertices $2$ and $3$, guarding all vertices.\n*   Place a takahashi at all vertices, guarding all vertices."},{"iden":"sample input 2","content":"5\n1 3\n4 5\n1 5\n2 3"},{"iden":"sample output 2","content":"1\n0\n2\n5\n7\n17"},{"iden":"sample input 3","content":"10\n6 10\n1 8\n2 7\n5 6\n3 8\n3 4\n7 10\n4 9\n2 8"},{"iden":"sample output 3","content":"1\n0\n3\n8\n15\n32\n68\n110\n196\n266\n325"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}