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 \leq N \leq 100\,000)~.
• N-1 dòng tiếp theo mỗi dòng gồm ~3~ số nguyên ~A~, ~B~ và ~W~ ~(1 \leq A~, ~B \leq N~, ~0 \leq W \leq 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 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 Output 2

90

Sample Input 3

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

Sample Output 3

55

Note

• Làm quen QHD trên cây, hoặc vừa DFS vừa tính toán - tính ứng dụng cao
• Task PUTEVI : Croatia Contest - Final Exam 08