| Codeforces Round 426 (Div. 1) |
|---|
| Закончено |
Сластене очень нравится наблюдать за жизнью обитателей тенистой рощи, находящейся неподалеку от Мармеладного замка. На этот раз ее вниманием завладел странный красно-черный желейный паук, восседающий в центре огромной паутины.
Паутина странного паука представляет собой набор из n узлов, соединенных прочными нитями, каждая из которых покрашена либо в красный, либо в черный цвет. Используя эти нити, паук перемещается между узлами паутины, причем ни одна нить не соединяет узел с самим собой и для любых двух различных узлов существует единственная последовательность нитей, их соединяющая.
Как настоящий энтузиаст, Сластена начала исследовать замечательные свойства паутины. После нескольких часов наблюдения Сластена заметила, что каждая нить имеет собственное значение клейкости x, что само по себе удивительный факт.
Но больше всего Сластену интересует желейность данной паутины. Рассмотрим те из кратчайших путей между всеми парами узлов в паутине, на которых количество нитей каждого цвета отличается не более, чем вдвое. Для каждого такого пути посчитаем произведение клейкостей всех нитей на пути. Желейностью паутины Сластена называет произведение всех полученных величин по всем путям. Из путей, отличающихся только направлением движения, учитывается только один.
Естественно, данное число очень большое, а Сластена большие числа не любит. Поэтому она просит вас посчитать желейность данной паутины и вывести ответ по модулю 109 + 7.
В первой строке задано число узлов паутины n (2 ≤ n ≤ 105).
В следующих n - 1 строках следуют по четыре числа, описывающие i-ю нить паутины: узлы ui, vi (1 ≤ ui ≤ n, 1 ≤ vi ≤ n), клейкость нити xi (1 ≤ x ≤ 109 + 6), а также цвет нити ci (
). Красный цвет задается числом 0, а черный цвет — числом 1.
Выведите единственное число — желейность паутины по модулю 109 + 7. Если не существует путей таких, что число красных и черных нитей отличается не более, чем вдвое, выведите 1.
5
1 2 9 0
2 3 5 1
2 4 5 0
2 5 5 1
1265625
8
1 2 7 1
2 3 4 1
3 4 19 1
5 1 2 0
6 2 3 0
7 3 3 0
8 4 4 0
452841614
В первом примере существует 4 пары узлов, количество нитей двух цветов между которыми отличается не более, чем вдвое. Это пары (1, 3) с произведением клейкостей на пути 45, (1, 5) с произведением клейкостей на пути 45, (3, 4) с произведением клейкостей на пути 25 и (4, 5) с произведением клейкостей на пути 25. Желейность такой паутины равняется 1265625.
