{"problem":{"name":"Surrounded Nodes","description":{"content":"Given is a tree $T$ with $N$ vertices. The $i$\\-th edge connects Vertex $A_i$ and $B_i$ ($1 \\leq A_i,B_i \\leq N$). Now, each vertex is painted black with probability $1/2$ and white with probability $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc149_f"},"statements":[{"statement_type":"Markdown","content":"Given is a tree $T$ with $N$ vertices. The $i$\\-th edge connects Vertex $A_i$ and $B_i$ ($1 \\leq A_i,B_i \\leq N$).\nNow, each vertex is painted black with probability $1/2$ and white with probability $1/2$, which is chosen independently from other vertices. Then, let $S$ be the smallest subtree (connected subgraph) of $T$ containing all the vertices painted black. (If no vertex is painted black, $S$ is the empty graph.)\nLet the _holeyness_ of $S$ be the number of white vertices contained in $S$. Find the expected holeyness of $S$.\nSince the answer is a rational number, we ask you to print it $\\bmod 10^9+7$, as described in Notes.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i,B_i \\leq N$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$:$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]\n\n## Notes\n\nWhen you print a rational number, first write it as a fraction $\\frac{y}{x}$, where $x, y$ are integers, and $x$ is not divisible by $10^9 + 7$ (under the constraints of the problem, such representation is always possible).\nThen, you need to print the only integer $z$ between $0$ and $10^9 + 6$, inclusive, that satisfies $xz \\equiv y \\pmod{10^9 + 7}$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc149_f","tags":[],"sample_group":[["3\n1 2\n2 3","125000001\n\nIf the vertices $1, 2, 3$ are painted black, white, black, respectively, the holeyness of $S$ is $1$.\nOtherwise, the holeyness is $0$, so the expected holeyness is $1/8$.\nSince $8 \\times 125000001 \\equiv 1 \\pmod{10^9+7}$, we should print $125000001$."],["4\n1 2\n2 3\n3 4","375000003\n\nThe expected holeyness is $3/8$.\nSince $8 \\times 375000003 \\equiv 3 \\pmod{10^9+7}$, we should print $375000003$."],["4\n1 2\n1 3\n1 4","250000002\n\nThe expected holeyness is $1/4$."],["7\n4 7\n3 1\n2 6\n5 2\n7 1\n2 7","570312505"]],"created_at":"2026-03-03 11:01:14"}}