The country of IOI consists of $N$ cities and $N-1$ bidirectional railways connecting them, such that any two distinct cities can be reached from each other using only the railways. In other words, the railway network of IOI forms a tree structure. The cities are labeled with distinct integers from $0$ to $N-1$, and the railways are labeled with distinct integers from $0$ to $N-2$. For all $0 \le i \le N-2$, the $i$-th railway connects city $U[i]$ and city $V[i]$ bidirectionally, and the length of the railway is $W[i]$.

From any city in the country of IOI, one can travel directly to any other city by taking a direct train. That is, for all $N(N-1)$ ordered pairs $(u, v)$ such that $0 \le u, v \le N-1$ and $u \neq v$, there is a direct train from city $u$ to city $v$. Once you board this direct train at city $u$, you cannot get off until you arrive at city $v$. The travel time of this direct train is equal to the sum of the lengths of the railways on the unique simple path starting at city $u$ and ending at city $v$ in the railway network of IOI.

As a railway enthusiast, you enjoy the relaxation of riding a train for a long time, so you feel greater joy the longer the travel time of the direct trains you take.

Specifically, for two distinct cities $x$ and $y$, the joy $joy(x, y)$ is defined as the maximum positive integer $D$ that satisfies the following condition:

• You can reach city $y$ from city $x$ by repeating a finite number of times the action of taking a direct train with a travel time of at least $D$.

Write a program that calculates the sum of $joy(x, y)$ for all $N(N-1)$ ordered pairs $(x, y)$ satisfying $0 \le x, y \le N-1$ and $x \neq y$, modulo $1\,000\,000\,007$ ($= 10^9 + 7$).

Implementation Details

You must implement the following function:

int travel(vector<int> U, vector<int> V, vector<int> W)

• This function is called exactly once.
• $U, V, W$: Integer arrays of size $N-1$. For all $i$ ($0 \le i \le N-2$), there is a railway of length $W[i]$ connecting city $U[i]$ and city $V[i]$.
• This function must return the sum of $joy(x, y)$ for all $N(N-1)$ ordered pairs $(x, y)$ satisfying $0 \le x, y \le N-1$ and $x \neq y$, modulo $1\,000\,000\,007$ ($= 10^9 + 7$).

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $2 \le N \le 500\,000$
• The railway network of IOI forms a tree structure.
• For all $i$, $0 \le U[i], V[i] \le N-1$; $U[i] \neq V[i]$ ($0 \le i \le N-2$)
• For all $i$, $1 \le W[i] \le 1\,000\,000\,000$ ($0 \le i \le N-2$)

Subtasks

1. (3 points) $N \le 50$
2. (6 points) $N \le 500$
3. (19 points) $N \le 2\,000$
4. (5 points) $N \le 8\,000$, $U[i] = 0$ for all $i$ ($0 \le i \le N-2$)
5. (7 points) $N \le 8\,000$, $U[i] = i, V[i] = i+1$ for all $i$ ($0 \le i \le N-2$)
6. (15 points) $N \le 8\,000$
7. (4 points) $U[i] = 0$ for all $i$ ($0 \le i \le N-2$)
8. (11 points) $U[i] = i, V[i] = i+1$ for all $i$ ($0 \le i \le N-2$)
9. (30 points) No additional constraints.

Examples

Input 1

5
0 1 1
1 2 2
0 3 3
0 4 2

Output 1

80

Note

The example above corresponds to $N=5$, $U=[0, 1, 0, 0]$, $V=[1, 2, 3, 4]$, $W=[1, 2, 3, 2]$.

Input 2

5
0 1 3
0 2 2
0 3 2
0 4 1

Output 2

78

Note

The example above corresponds to $N=5$, $U=[0, 0, 0, 0]$, $V=[1, 2, 3, 4]$, $W=[3, 2, 2, 1]$.

Input 3

6
0 1 3
1 2 1
2 3 4
3 4 1
4 5 5

Output 3

284

Note

The example above corresponds to $N=6$, $U=[0, 1, 2, 3, 4]$, $V=[1, 2, 3, 4, 5]$, $W=[3, 1, 4, 1, 5]$.

Sample Grader

The sample grader receives input in the following format:

• Line 1: $N$
• Line 2 + $i$ ($0 \le i \le N-2$): $U[i] \ V[i] \ W[i]$

The sample grader outputs the following:

• Line 1: The value returned by travel

Note that the sample grader may differ from the grader used for actual evaluation.