Problem Description

You are given a tree with $n$ nodes.

Define $f(u, v, i)$ as the minimum value of $\text{dis}(x, i)$ among all points $x$ that satisfy $\text{dis}(u, x) + \text{dis}(v, x) = \text{dis}(u, v)$.

Compute the value of $\sum\limits_{u = 1}^n \sum\limits_{v = u + 1}^n \sum\limits_{i = 1}^n f(u, v, i)$ modulo $10^9 + 7$.

$\text{dis}(u, v)$ denotes the path length between nodes $u$ and $v$ on the tree. Specifically, $\text{dis}(u, u) = 0$.

Input Format

The first line contains an integer $n$, representing the number of nodes in the tree.

The next $n - 1$ lines each contain two integers $u_i$ and $v_i$, indicating an edge in the tree.

Output Format

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

4
1 2
1 3
1 4

Sample Output #1

9

Sample Input #2

6
1 2
2 3
3 4
4 5
5 6

Sample Output #2

70

Sample Input #3

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

Sample Output #3

536

Notes

Sample Explanation

In Sample 1, the values of $f(u, v, i)$ that are not zero are:

• $f(1, 2, 3) = 1$;
• $f(1, 2, 4) = 1$;
• $f(1, 3, 2) = 1$;
• $f(1, 3, 4) = 1$;
• $f(1, 4, 2) = 1$;
• $f(1, 4, 3) = 1$;
• $f(2, 3, 4) = 1$;
• $f(2, 4, 3) = 1$;
• $f(3, 4, 2) = 1$.

Data Range

This problem uses batched testing and has subtask dependencies enabled.

For all data, $2 \le n \le 2 \cdot 10^5$, and the input graph is a tree.

见题面 Input 部分

见题面 Output 部分