Today is Explorer's birthday, and two of his best friends Raful and Jambo gave him a tree with N vertices and N−1 edges. After playing with it for a while, Explorer got bored, so Raful and Jambo gave him a task:
find the answer A modulo 109+7 - sum of all functions f(u,v) for all unordered pairs of vertices (u,v) such that u!=v. The function f(u,v) is the product of the weights of the edges on the shortest path between u and v. Note that pairs (u,v) and (v,u) are considered the same, so must only be counted once.
He easily solved it. Can you (the best programmer in Lalalandia) do it too?
Input format
The first line contains one integer N - the number of vertices.
The next N−1 lines describe the edges: each contains three integers u, v and c. This means that there is the edge with weight c between vertices u and v.
Output format
The first line should contain the single integer A modulo 109+7 - sum of all functions f(u,v).
Constraints:
1≤N≤5∗105
1≤u,v≤N
1≤c≤109
There are 6 unordered unique pairs: (1,2),(1,3),(1,4),(2,3),(2,4),(3,4), so the answer is 2+6+1+3+2+6=20.
