Description

彼得是一个生物专家，他从不同的资料中分析同一群物种间的演化关系，经常会得到不同的演化树，他想知道不同演化树间的相似程度。为了节省比较时间，他的想法是先将每一棵演化树 $T$ 的结构用一个称为「指纹 (fingerprint)」的数字来表示，然后再进一步去仔细比较「指纹」相近的不同演化树。

演化树是一棵无向无根树 (undirected, unrooted tree)，叶节点代表现存物种。令 $S$ 是一个现存物种集合，令 $T$ 是 $S$ 的一棵演化树；也就是说 $T$ 的叶节点集合是 $S$；令 $\text{deg}(x)$ 表示与节点 $x$ 相邻之节点个数，对于一个点 $x \in T$，当 $\text{deg}(x) = 1$ 时，我们称 $x$ 为 $T$ 的叶节点；而不是叶节点的点就称作内节点，代表着物种的演化过程。对任两个物种 $x, y\in S$，定义它们间的距离 $d(x, y)$ 为 $x$ 到 $y$ 路径 (path) 上的边数 (number of edges)。彼得用 $f(T)$ 来表示 $T$ 的「指纹」并定义 $T$ 的「指纹」为任两物种距离平方的总和；也就是说

$$f(T) = \sum_{x, y \in S, x < y} d(x, y)^2。$$

以下图中的演化树 $T$ 为例，这个演化树的「指纹」 $f(T) = d(1, 2)^2 + d(1, 3)^2 + d(1, 4)^2 + d(1, 5)^2 + d(2, 3)^2 + d(2, 4)^2 + d(2, 5)^2 + d(3, 4)^2 + d(3, 5)^2 + d(4, 5)^2 = 3^2 + 3^2 + 3^2 + 3^2 + 4^2 + 4^2 + 2^2 + 2^2 + 4^2 + 4^2 = 108$。

:::align{center} :::

请撰写一个程序来计算一棵演化树 $T$ 的「指纹」 $f(T)$。因为 $f(T)$ 可能很大，所以你只要求出 $f(T)$ 除以 $10^9 + 7$ 的余数。

Input Format

$$\begin{aligned} &m \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{m-1} \ v_{m-1} \end{aligned}$$

• $m$ 代表演化树 $T$ 的点数量。
• $u_i$ 和 $v_i$ 代表的是在 $T$上 $u_i$ 和 $v_i$ 有一条边。

Output Format

$$a$$

• $a$ 代表给定的演化树 $T$ 的指纹除以 $10^9 + 7$ 的余数。

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

108

2
1 2

1

Hint

数据限制

• $2 \le m \le 10^6$。
• $1 \le u_i, v_i \le m$。
• 输入的数皆为整数。
• 保证给定的图是一棵连通的演化树。

评分说明

本题共有三组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	7	$m \le 1000$。
2	31	演化树的所有内部节点 $v$ 的 deg($v$) 都等于 $3$，$m \le 10^5$。
3	62	无额外限制。