{"problem":{"name":"Tree Patrolling","description":{"content":"You have a tree with $N$ vertices, numbered $1$ through $N$. The $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$. You will choose some vertices (possibly none) and place a takahashi in each of the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc207_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc207_f","tags":[],"sample_group":[["3\n1 3\n1 2","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."],["5\n1 3\n4 5\n1 5\n2 3","1\n0\n2\n5\n7\n17"],["10\n6 10\n1 8\n2 7\n5 6\n3 8\n3 4\n7 10\n4 9\n2 8","1\n0\n3\n8\n15\n32\n68\n110\n196\n266\n325"]],"created_at":"2026-03-03 11:01:14"}}