You are given a weighted tree with \(N\) nodes and \(N - 1\) edges.

\(E\) is defined as \(\sum_\limits{i=1}^{i = N} \sum_\limits{j=i +1}^{j = N} F(i,j)\). Also, \(F(i, j)\) is equal to = (Maximum value of the edge that is present on the simple path between node \(i\) and \(j\)) \(\times i \times j\)

You are required to determine the value of \(E\) modulo \(10^9 + 7\).

Input format

• The first line contains an integer \(N\) denoting the number of nodes in a tree.
• The next \(N - 1\) lines contain three space-separated integers \(u, v, w\) denoting an edge between node \(u\) and \(v\) with weight \(w\).

Output format

Print the required value of \(E\) modulo \(10^9 + 7\).

Constraints