問題文

$N$ 頂点の木が与えられます。$i$ 番目の辺は頂点 $u_i$ と $v_i$ を双方向に結び、その長さは $w_i$ です。

$d(x,y)$ を頂点 $x$ と $y$ の最短距離とします。

$\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}d(i,j)^2$ を求めてください。

これは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。

入力

$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$
• 与えられるグラフは木
• 入力は全て整数

出力

$\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}d(i,j)^2$ を $10^9+7$ で割った余りを出力してください。

最後に改行してください。

サンプル

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