問題文

$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\le N\le 2\times {10}^5$
• $1\le u_i,v_i\le N$
• $u_i\ne v_i$
• $1\le w_i\le {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