# HDU 6446 Tree and Permutation

• 2018-08-27
• 48
• 0

## 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.

3
1 2 1
2 3 1
3
1 2 1
1 3 2

16
24

3
1 2 1
2 3 1

3
1 2 1
1 3 2

cnt[2]=2
cnt[3]=4
cnt[4]=12
cnt[5]=48
cnt[6]=240
cnt[7]=1440
cnt[8]=10080
cnt[9]=80640
cnt[10]=725760
cnt[11]=7257600