Cho một Cây (cây là đồ thị vô hướng, liên thông, không chu trình) có \(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 của đường đi đó. 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ừ đỉnh \(A\) tới đỉnh \(B\) và từ đỉnh \(B\) tới đỉnh \(A\) được coi là duy nhất, chỉ \(1\) lần. Hãy tính trọng số của cây được cho. Vì kết quả có thể rất lớn, chỉ cần tính và in ra số dư của nó khi chia cho \(10^9+7\).

Input

• Dòng đầu là một số nguyên dương \(N\) - số đỉnh của cây;
• \(N-1\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(A,\ B,\ W\) (\(1\leq A,B\leq N,\ 0\leq W\leq1000\)) - mô tả một cạnh nối giữa hai đỉnh \(A,B\), có trọng số \(W\).

Output

• Trọng số của cây theo modulo \(10^9+7\).

Examples

Sample input

2
1 2 3
1 3 4

Sample output

19

Subtasks

• Có \(50\%\) test tương ứng với \(50\%\) số điểm có \(N\leq1000\);
• Có \(50\%\) test còn lại tương ứng với \(50\%\) số điểm có \(N\leq10^5\);