Problem Statement

You are given a tree with $N$ vertices. The $i$-th edge bidirectionally connects vertices $u_i$ and $v_i$, and its length is $w_i$.

Let $d(x,y)$ be the shortest distance between vertices $x$ and $y$.

Find $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}d(i,j)^2$.

Since this value can be very large, print the remainder when it is divided by $10^9+7$.

Input

$N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$︙$
$u_{N-1}\ v_{N-1}\ w_{N-1}$

• $1≤N≤2×10^5$
• $1≤u_i,\ v_i≤N$
• $u_i≠v_i$
• $1≤w_i≤10^9$
• The given graph is a tree.
• All input values are integers.

Output

Print the remainder when $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}d(i,j)^2$ is divided by $10^9+7$.

Print a newline at the end.

Sample

3
1 2 1
2 3 2

14

5
1 3 4
2 5 3
3 4 9
5 4 1

1046

6
3 5 192329
4 6 293129
6 2 129532
1 2 39237
6 3 57325762

219459352