题目描述

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$，并有 $N-1$ 条边，边的编号为 $1$ 到 $N-1$。第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$，且每条边的长度为 $1$。

すぬけ君要将每个顶点涂成白色或黑色。对于一种涂色方案，定义其“优良度”为：所有白色顶点之间的距离最大值为 $X$，所有黑色顶点之间的距离最大值为 $Y$，则该方案的优良度为 $\max(X, Y)$。如果某种颜色的顶点不存在，则该颜色的距离最大值视为 $0$。

顶点的涂色方法共有 $2^N$ 种。请计算所有涂色方法的优良度之和，并对 $10^9+7$ 取模。

输入格式

输入通过标准输入给出，格式如下：

$N$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

输出格式

请输出所有涂色方法的优良度之和对 $10^9+7$ 取模的结果。

样例 1

输入

2
1 2

输出

2

样例 2

输入

6
1 2
2 3
3 4
4 5
3 6

输出

224

样例 3

输入

35
25 4
33 7
11 26
32 4
12 7
31 27
19 6
10 22
17 12
28 24
28 1
24 15
30 24
24 11
23 18
14 15
4 29
33 24
15 34
11 3
4 35
5 34
34 2
16 19
7 18
19 31
22 8
13 26
20 6
20 9
4 33
4 8
29 19
15 21

输出

298219707

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i, b_i \leq N$
• 给定的图为一棵树。

样例解释 1

• 当顶点 $1,2$ 都涂成同一种颜色时，优良度为 $1$；当涂成不同颜色时，优良度为 $0$。所有涂色方法的优良度之和为 $2$。

样例解释 3

• 别忘了对 $10^9+7$ 取模。

由 ChatGPT 4.1 翻译