Giải bài trực tuyến

Cho một cây N đỉnh, N-1 cạnh. Mỗi cạnh được gán 1 số không âm. Trọng số của một đường đi là tích các số ghi trên cạnh. Trọng số của cây là tổng trọng số của mọi đường đi giữa mọi cặp đỉnh trên cây. Đường đi từ 2 nút A tới B và B tới A được coi là duy nhất, chỉ tính 1 lần.

Cho 1 cây, tính số dư trọng số của cây cho 1000000007.

Input

Dòng đầu là số đỉnh của cây - N (2 ≤ N ≤ 100 000). N-1 dòng tiếp theo mỗi dòng gồm 3 số nguyên A, B và W (1 ≤ A, B ≤ N, 0 ≤ W ≤ 1000) mô tả cạnh nối hai đỉnh A, B có trọng số W.

Output

Trọng số của cây theo module 1000000007.

Sample

input 
3 
3 2 100 
2 1 100 
 
output 
10200 

input 
4 
1 2 5 
1 3 5 
1 4 5 
 
output 
90 

input 
5 
1 2 2 
2 3 3 
4 3 2 
5 3 2 
 
output 
55