Home

Problem Statement

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 $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.)

Let the holeyness of $S$ be the number of white vertices contained in $S$. Find the expected holeyness of $S$.

Since the answer is a rational number, we ask you to print it $\bmod 10^9+7$, as described in Notes.

Notes

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).

Then, you need to print the only integer $z$ between $0$ and $10^9 + 6$, inclusive, that satisfies $xz \equiv y \pmod{10^9 + 7}$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i,B_i \leq N$
• The given graph is a tree.

Sample Input 1

3
1 2
2 3

Sample Output 1

125000001

If the vertices $1, 2, 3$ are painted black, white, black, respectively, the holeyness of $S$ is $1$.

Otherwise, the holeyness is $0$, so the expected holeyness is $1/8$.

Since $8 \times 125000001 \equiv 1 \pmod{10^9+7}$, we should print $125000001$.

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

375000003

The expected holeyness is $3/8$.

Since $8 \times 375000003 \equiv 3 \pmod{10^9+7}$, we should print $375000003$.

Sample Input 3

4
1 2
1 3
1 4

Sample Output 3

250000002

The expected holeyness is $1/4$.

Sample Input 4

7
4 7
3 1
2 6
5 2
7 1
2 7

Sample Output 4

570312505