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 109+7.
### Constraints
- 1≤n≤105.
- 1≤u,v≤n.
- 1≤w≤109.
### Example
Input:
5122233432532
Output:
55
