{"raw_statement":[{"iden":"problem statement","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."},{"iden":"notes","content":"When 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}$."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i,B_i \\leq N$\n*   The given graph is a tree."},{"iden":"input","content":"Input 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}$"},{"iden":"sample input 1","content":"3\n1 2\n2 3"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"4\n1 2\n2 3\n3 4"},{"iden":"sample output 2","content":"375000003\n\nThe expected holeyness is $3/8$.\nSince $8 \\times 375000003 \\equiv 3 \\pmod{10^9+7}$, we should print $375000003$."},{"iden":"sample input 3","content":"4\n1 2\n1 3\n1 4"},{"iden":"sample output 3","content":"250000002\n\nThe expected holeyness is $1/4$."},{"iden":"sample input 4","content":"7\n4 7\n3 1\n2 6\n5 2\n7 1\n2 7"},{"iden":"sample output 4","content":"570312505"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}