题目描述

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.

给出一棵树 $T$ ，有 $N$ 个顶点。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$ ( $1 \leq A_i,B_i \leq N$ )。

现在，每个顶点都被涂成黑色，概率为 $1/2$ ，涂成白色的概率为 $1/2$ ，与其他顶点无关。那么，假设 $S$ 是包含所有涂黑顶点的 $T$ 的最小子树（连通子图）。(如果没有顶点涂黑， $S$ 就是空图）。

设 $S$ 的洞度为 $S$ 中包含的白色顶点的个数。求 $S$ 的期望洞度。

由于答案是有理数，因此请您按照注释中的说明打印出 $\bmod 10^9+7$ 。

输入格式

输入内容按以下格式标准输入：

$N$
$A_1$ $B_1$
$:$
$A_{N-1}$ $B_{N-1}$

输出格式

打印 $S$ , $\bmod 10^9+7$ 的预期洞度。

样例 #1

样例输入 #1

3
1 2
2 3

样例输出 #1

125000001

样例 #2

样例输入 #2

4
1 2
2 3
3 4

样例输出 #2

375000003

样例 #3

样例输入 #3

4
1 2
1 3
1 4

样例输出 #3

250000002

样例 #4

样例输入 #4

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

样例输出 #4

570312505

说明

打印有理数时，首先将其写成分数 $\frac{y}{x}$ ，其中 $x, y$ 是整数，而 $x$ 不能被 $10^9 + 7$ 整除（在问题的限制条件下，这样的表示总是可能的）。

然后，您需要打印出 $0$ 和 $10^9 + 6$ 之间唯一满足 $xz \equiv y \pmod{10^9 + 7}$ 的整数 $z$ 。

数据规模与约定

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i,B_i \leq N$
• 给定的图形是一棵树。

样例 $1$ 解释

如果将顶点 $1, 2, 3$ 分别涂成黑色、白色、黑色，那么 $S$ 的洞度为 $1$ 。

否则，洞度为 $0$ ，因此预期洞度为 $1/8$ 。

由于 $8 \times 125000001 \equiv 1 \pmod{10^9+7}$ ，我们应该打印 $125000001$ 。

样例 $2$ 解释

预期洞度为 $3/8$ 。

由于 $8 \times 375000003 \equiv 3 \pmod{10^9+7}$ ，我们应该打印 $375000003$ 。

样例 $3$ 解释

预期洞度为 $1/4$ 。