In the distant future, humanity has expanded to numerous alien planets. Planet X is one of them, where the space exploration company MR has built bases to conduct exploration and resource extraction activities.

Planet X has $N$ bases and $N-1$ bidirectional passages connecting them, such that any two distinct bases can be reached from each other using only the passages. In other words, the bases and passages of Planet X form a tree structure.

Each base is assigned a unique number from $0$ to $N-1$. For all $0 \le i \le N-2$, the $i$-th passage connects base $U[i]$ and base $V[i]$ with a length of $W[i]$ km.

As the development of Planet X has entered a stable phase, maintaining all bases and passages has become costly. Therefore, MR has decided to keep only some bases and deactivate the rest.

Suppose that for some $(s, e)$ ($0 \le s \le e \le N-1$), only bases $s, s+1, \dots, e$ are to be kept. The maintenance cost is defined as follows:

• Select zero or more passages to satisfy the following condition. The passages are chosen such that the sum of their lengths is minimized. (If zero passages are chosen, the sum of lengths is $0$ km.)
  • For any $u, v$ ($s \le u < v \le e$), base $u$ and base $v$ can reach each other using only the chosen passages. It does not matter if deactivated bases are traversed in between.
• If the sum of the lengths of the chosen passages is $C$ km, the maintenance cost is $C$.

Since it has not yet been decided which bases to keep, MR wants to know the sum of the maintenance costs for all possible pairs $(i, j)$ ($0 \le i \le j \le N-1$) when only bases $i, i+1, \dots, j$ are kept. You must calculate this value for MR. Since the value can be very large, you must find the remainder when divided by $1\,000\,000\,007$.

Implementation Details

You must implement the following function:

int maintenance_costs_sum(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 passage of length $W[i]$ km connecting base $U[i]$ and base $V[i]$.
• This function must return the sum of the maintenance costs for all possible pairs $(i, j)$ ($0 \le i \le j \le N-1$) when only bases $i, i+1, \dots, j$ are kept, modulo $1\,000\,000\,007$.

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

Constraints

• $2 \le N \le 250\,000$
• $0 \le U[i], V[i] \le N-1$ and $U[i] \neq V[i]$ for all $i$ ($0 \le i \le N-2$)
• $1 \le W[i] \le 10^9$ for all $i$ ($0 \le i \le N-2$)

Subtasks

1. (5 points) $N \le 300$
2. (6 points) $N \le 4\,000$
3. (10 points) The numbers assigned to the bases correspond to one of the preorder traversal sequences of the tree rooted at base 0.
4. (26 points) Each base is connected to at most 2 passages.
5. (53 points) No additional constraints.

Examples

Input 1

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

Output 1

98

The maintenance costs for all possible $(i, j)$ pairs are given in the table below: