You are given a weighted tree consisting of $n$ vertices.
The weight of a path is the product of the weights of edges on the path. The weight of a tree is the sum of all path weights. The path from $u$ to $v$ and $v$ to $u$ are considered the same.
Find the weight of the given tree.
### Input
- The first line contains an integer $n$.
- The next $n - 1$ lines, each line contains 3 integers $u,v, w$, there is an edge of weight between $u$ and $v$.
### Output
- Print the weight of the given tree, modulo $10^9+7$.
### Constraints
- $1 \le n \le 10^5$.
- $1 \le u, v \le n$.
- $1 \le w \le 10^9$.
### Example
Input:
```
5
1 2 2
2 3 3
4 3 2
5 3 2
```
Output:
```
55
```
