Хайди в ужасе от шутки, и она сочла нереальным, что ее друзья будут специально загонять её в долги. Она ожидает, что фактически, каждый человек просто выберет случайного друга, чтобы отправить Хайди. Из этого следует, что теперь Хайди может посещать одного и того же друга произвольное количество раз. Более того, если у человека есть ровно один общий друг с Хайди (то есть он является листом дерева), тогда этот человек не отправит Хайди обратно (то есть путешествие Хайди закончится в некоторой точке).
Хайди также кажется нереальным то, что она сможет совершить свое путешествие за один день. Поэтому теперь она предполагает, что каждый раз, когда она путешествует по маршруту между двумя друзьями, ей нужно покупать новый билет. Она хочет знать математическое ожидание суммы денег, которые она потратит на путешествия.
Полагайте, что у Дженни есть по крайней мере два друга.
В первой строке следует целое число n (3 ≤ n ≤ 105) — количество друзей.
В следующих n - 1 строках следует по три целых числа u, v и c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104), означающих что u и v являются друзьями и стоимость путешествий между ними равна c (для каждого нового путешествия между ними теперь нужно покупать новый билет).
Гарантируется, что дружеские связи из входных данных формируют дерево.
Предположим, что ожидаемая стоимость путешествий записывается как несократимая дробь a / b (то есть, a и b являются взаимно простыми). Хайди просит вас вывести величину 
. То есть, выводимое число должно быть в пределах от 0 до 109 + 6, включительно.
3
0 1 10
0 2 20
15
4
0 1 3
0 2 9
0 3 27
13
7
0 1 3
0 5 7
1 2 2
1 3 1
1 4 5
5 6 8
400000019
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
153869806
6
0 1 8
0 2 24
1 3 40
1 4 16
4 5 8
39
В первом примере с вероятностью 1 / 2 Хайди пойдет в 1 из 0, и с вероятностью 1 / 2 она пойдет в 2. В первом случае стоимость будет 10, а во второй она будет 20. Достигнув 1 или 2 она остановится, так 1 и 2 являются листьями дерева. Следовательно, ожидаемые расходы Хайди на путешествия составляют 10·1 / 2 + 20·1 / 2 = 15.
В третьем примере ожидаемая стоимость составляет 81 / 5. Поэтому нужно вывести число 400000019.
В ходе своих путешествий Хайди узнала интригующий факт о структуре своих дружеских связей. Она сообщает вам следующее: Таинственный определитель, о котором вы могли бы подумать, таков, что он не вызывает странных ошибок в вашем разумном решении... Мы упоминали, что Хайди - странная корова?
