Sum of Tree Path Weights

Time limit2sMemory limit128 MB

Summary

Given a weighted tree, compute the sum over all vertex pairs of the product of edge weights along their connecting path, modulo 1e9+7.

Level: Medium6 of 10
Topics: Tree, DFS, Dynamic programming, Math
Solved: No attempts yet

Problem

You are given a tree with N vertices and N - 1 edges. In a tree, there is exactly one simple path between any two distinct vertices.

Each edge has a non-negative integer weight. The weight of a path is defined as the product of the weights of all edges on that path. The weight of the tree is the sum of the weights of all paths connecting pairs of distinct vertices.

Given the tree, compute its weight.

Input

The first line contains the number of vertices N. (1 <= N <= 100,000)

Each of the next N - 1 lines contains three integers A B W. This means vertices A and B are connected by an edge with weight W. (1 <= A, B <= N, 0 <= W <= 1,000)

Output

Print the weight of the tree modulo 1,000,000,007.

Examples3

Example 1
Input
```
3
3 2 100
2 1 100
```
Expected output
```
10200
```
Example 2
Input
```
4
1 2 5
1 3 5
1 4 5
```
Expected output
```
90
```
Example 3
Input
```
5
1 2 2
2 3 3
4 3 2
5 3 2
```
Expected output
```
55
```