题目描述

给定一个有 $N$ 个顶点，编号从 $1$ 到 $N$，以及 $N-1$ 条边，编号从 $1$ 到 $N-1$ 的树。第 $i$ 条边双向连接了顶点 $a_i$ 和 $b_i$，边长为 $1$。

Snuke 将每个顶点涂成白色或黑色。涂色方式的“美好程度”定义为 $\\max(X, Y)$，其中 $X$ 是所有白色顶点之间的距离的最大值，$Y$ 是所有黑色顶点之间的距离的最大值。如果其中一种颜色的顶点不存在，则将该颜色顶点之间的距离的最大值定义为 $0$。

总共有 $2^N$ 种涂色方式。计算所有涂色方式的美好程度之和除以 $(10^{9}+7)$ 所得的余数。

约束条件

• $2 \\leq N \\leq 2 \\times 10^{5}$
• $1 \\leq a_i, b_i \\leq N$
• 给定的图是一棵树。

输入

从标准输入读入输入数据的格式如下：

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

输出

打印所有涂色方式的美好程度之和除以 $(10^{9}+7)$ 所得的余数。

示例输入 1

2
1 2

示例输出 1

2

• 如果将顶点 $1$ 和 $2$ 涂成相同的颜色，则美好程度为 $1$；如果将它们涂成不同的颜色，则美好程度为 $0$。
• 这些美好程度之和为 $2$。

示例输入 2

6
1 2
2 3
3 4
4 5
3 6

示例输出 2

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

示例输出 3

298219707

• 计算时请务必对 $(10^{9}+7)$ 取模。