All Submissions


As you are bound to know by now, a tree is a connected graph consisting of N vertices and N-1 edges. Trees also have the property of there being exactly a single unique path between any pair of vertices.
You will be given a tree in which every edge is assigned a weight ; a non negative integer. The weight of a path is the product of the weights of all edges on the path. The weight of the tree is the sum of the weights of all paths in the tree. Paths going in opposite directions (A to B and B to A) are considered the same and, when calculating the weight of a tree, are counted only once.
Write a program that, given a tree, calculates its weight modulo 1000000007.

Input

The first line contains the integer N (2 <= N <= 100 000), the number of vertices
in the tree. The vertices are numbered 1 to N. Each of the following N-1
contains three integers A, B and W (1 <=A, B <= N, 0 <= W <= 1000)
describing one edge. The edge connects vertices A and B, and its weight is W.

Output

Output the weight of the tree, modulo 1000000007.

Sample Input 1


3
3 2 100
2 1 100


Sample Output 1


10200


Sample Input 2


4
1 2 5
1 3 5
1 4 5


Sample Input 2


90


Sample Input 3


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


Sample Input 3


55


Problem Setter : Kirti Vardhan Rathore

Languages: C,C++,Java

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0