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 $$10^9 + 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?
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$$.
The first line should contain the single integer $$A$$ modulo $$10^9 +7$$ - sum of all functions $$f(u, v)$$.
$$1 \le N \le 5 * 10^5$$
$$1 \le u, v \le N$$
$$1 \le c \le 10^9$$
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$$.