Send the Fool Further! (hard)

Description:

Input:

The first line contains the number of friends n (3 ≤ n ≤ 10⁵). The next n - 1 lines each contain three space-separated integers u, v and c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 10⁴) meaning that u and v are friends and the cost for traveling between u and v is c (paid every time!).

It is again guaranteed that the social network of the input forms a tree.

Output:

Assume that the expected cost of the trips is written as an irreducible fraction a / b (that is, a and b are coprime). Then Heidi, the weird cow that she is, asks you to output . (Output a single integer between 0 and 10⁹ + 6.)

Sample Input:

3
0 1 10
0 2 20

Sample Output:

15

Sample Input:

4
0 1 3
0 2 9
0 3 27

Sample Output:

13

Sample Input:

7
0 1 3
0 5 7
1 2 2
1 3 1
1 4 5
5 6 8

Sample Output:

400000019

Sample Input:

11
1 0 6646
2 0 8816
3 2 9375
4 2 5950
5 1 8702
6 2 2657
7 2 885
8 7 2660
9 2 5369
10 6 3798

Sample Output:

153869806

Sample Input:

6
0 1 8
0 2 24
1 3 40
1 4 16
4 5 8

Sample Output:

39

Note:

In the first example, with probability 1 / 2 Heidi will go to 1 from 0, and with probability 1 / 2 she will go to 2. In the first case the cost would be 10, and in the second it would be 20. After reaching 1 or 2 she will stop, as 1 and 2 are leaves of the social tree. Hence, the expected cost she has to pay is 10·1 / 2 + 20·1 / 2 = 15.

In the third example, the expected cost is 81 / 5. You should output 400000019.

In her travels, Heidi has learned an intriguing fact about the structure of her social network. She tells you the following: The mysterious determinant that you might be wondering about is such that it does not cause strange errors in your reasonable solution... Did we mention that Heidi is a weird cow?