# Tree and Permutation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

There are N vertices connected by N?1 edges, each edge has its own length.
The set { 1,2,3,…,N } contains a total of N! unique permutations, let’s say the i-th permutation is Pi and Pi,j is its j-th number.
For the i-th permutation, it can be a traverse sequence of the tree with N vertices, which means we can go from the Pi,1-th vertex to the Pi,2-th vertex by the shortest path, then go to the Pi,3-th vertex ( also by the shortest path ) , and so on. Finally we’ll reach the Pi,N-th vertex, let’s define the total distance of this route as D(Pi) , so please calculate the sum of D(Pi) for all N! permutations.

Input

There are 10 test cases at most.
The first line of each test case contains one integer N ( 1≤N≤105 ) .
For the next N?1 lines, each line contains three integer X, Y and L, which means there is an edge between X-th vertex and Y-th of length L ( 1≤X,Y≤N,1≤L≤109 ) .

Output

For each test case, print the answer module 109+7 in one line.

Sample Input

3

1 2 1

2 3 1

3

1 2 1

1 3 2

Sample Output

16

24

n=3时，三个点1,2,3,其中1,2共有4种方法得到，即1,2,3,和2,1,3,和3,1,2,和3,2,1

n=4时，三个点1,2,3,4,其中1,2共有12种方法得到，即1,2,3,4,和1,2,4,3,和2,1,3,4,和2,1,4,3,和3,1,2,4,和3,2,1,4和4,1,2,3,和4,2,1,3,和3,4,1,2,和4,3,1,2,和3,4,2,1,和4,3,2,1,

n=jie[n-1]*（n-1）。