空洞度

题目描述

给定有 $N$ 个顶点的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$（$1 \leq A_i,B_i \leq N$）。

将 $T$ 的每个顶点分别独立地以概率 $1/2$ 涂成黑色、以概率 $1/2$ 涂成白色，设包含所有涂黑顶点的 $T$ 的最小部分树（连通子图）为 $S$。（当没有涂黑的顶点时，$S$ 视为空图。）

将 $S$ 的空洞度定义为 $S$ 中白色顶点的个数。求 $S$ 的空洞度的期望值。

答案是有理数，因此请按注记所述以 $\bmod 10^9+7$ 输出。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出 $S$ 的空洞度的期望值对 $10^9+7$ 取模的结果。

样例

3
1 2
2 3

125000001

当顶点 $1,2,3$ 的颜色分别为黑、白、黑时，$S$ 的空洞度为 $1$。

其他涂法下 $S$ 的空洞度都为 $0$，因此空洞度的期望值为 $1/8$。

由 $8 \times 125000001 \equiv 1 \pmod{10^9+7}$，输出 $125000001$。

4
1 2
2 3
3 4

375000003

期望值为 $3/8$。

由 $8 \times 375000003 \equiv 3 \pmod{10^9+7}$，输出 $375000003$。

4
1 2
1 3
1 4

250000002

期望值为 $1/4$。

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

570312505

数据范围

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

提示

输出有理数时，首先将该有理数表示为分数 $\frac{y}{x}$。这里，$x,y$ 是整数，且 $x$ 不能被 $10^9+7$ 整除（在本问题的约束下，这样的表示一定存在）。

然后，输出满足 $xz \equiv y \pmod{10^9+7}$ 的唯一的、在 $0$ 到 $10^9+6$（含）之间的整数 $z$。