题目描述

给定一棵 $n$ 个点的树，每一个结点都可以是黑色或白色，每一条边的长度都为 1。 定义两个点的距离为两个点最短路径上边的条数，定义一棵树的价值，为同色点距离的最大值。 请求出在所有情况下，树的价值之和，对 $10^9 + 7$ 取模。

输入格式

从文件 tree.in 中读入数据。 第一行一个正整数 $n$。 接下来 $n - 1$ 行，每行两个数 $x,y$，表示树中的一条边。

输出格式

输出到文件 tree.out 中。 输出一行一个数，表示你的答案，对 $10^9 + 7$ 取模。

样例 1

2
1 2

2

样例解释 1

若两个点颜色相同，同色点距离最大值为 1。 若两个点颜色不同，同色点距离最大值为 0。

样例 2

6
1 2
2 3
3 4
4 5
3 6

224

样例 3

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。 该样例满足测试点 2 的限制。

样例 4

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。 该样例满足测试点 7～8 的限制。

数据范围与提示

对于所有测试点：$2 \leq n \leq 10^6$。 每个测试点的具体限制见下表：

特殊性质 A：第 $i$ 条边连接 $i$ 和 $i + 1$。

特殊性质 B：1 号点的度数为 $n - 1$。

特殊性质 C：1 号点度数 $> 2$，其它点度数不超过 2，所有度数为 1 的结点到 1 号点的距离相同。