402804: GYM100885 E Передача опыта

Как известно, Берляндия — хорошо развитая страна, а поэтому в каждом городе есть школа. На недавнем съезде учителей стало ясно, что методики преподавания различных предметов во всех школах разные. Чтобы исправить это недоразумение, а также для улучшения качества образования было решено, что школам необходимо обмениваться опытом. Так как школы действительно разные, и у каждой имеется уникальный опыт, поступило предложение из каждой школы в каждую другую отправить делегата для перенимания опыта.

К сожалению, города в Берляндии находятся далеко друг от друга, поэтому их связывает минимальная возможная сеть дорог: из каждого города можно добраться по дорогам в любой другой не посещая ни один город дважды, но при этом лишь единственным способом. Также, еще большую проблему для учителей создает сложная система оплаты проезда по дорогам Берляндии.

Каждой дорогой владеет одна из K компаний, и для проезда по дорогам любой компании человек должен один раз купить проездной у этой компании. После этого он может проезжать по любым дорогам этой компании без дополнительной платы. Стоимость проездного i-ой компании (1 ≤ i ≤ K) равна c_i бурлей.

Каждому из делегатов нужно купить необходимые ему проездные. Помогите учителям посчитать, сколько же всего бурлей будут стоить все проездные для всех делегатов. Так как это число может быть большим, найдите остаток от деления этого числа на 1 000 000 007 (10⁹ + 7).

В первой строке входных данных находятся два натуральных числа N и K (1 ≤ N ≤ 1 500 000, 1 ≤ K ≤ 1 500 000) — число городов в Берляндии и число компаний-владельцев дорог соответственно. На следующих (N - 1) строках дано описание дорог Берляндии, на i-ой из этих строк (эти строки нумеруются с единицы, города тоже нумеруются с единицы) находятся два числа b_i и t_i (1 ≤ b_i ≤ N, 1 ≤ t_i ≤ K), означающие, что существует дорога из города с номером i + 1 в город с номером b_i, и владеет ей компания с номером t_i. По всем дорогам можно передвигаться в обе стороны; также, гарантируется, что из любого города можно добраться в любой другой по существующим дорогам.

На последней строке входных данных находятся 4 числа A, B, C, c₀ (1 ≤ C ≤ 1 000 000 001, 0 ≤ A, B, c₀ < C), задающие стоимости проездных. Стоимости проездных вычисляются по формуле , где c_i — стоимость проездного i-ой компании, а «» — остаток от деления X на Y.

Выведите единственное число — остаток от деления суммарной стоимости необходимых проездных на 1 000 000 007.

3 2
1 1
2 2
1 2 100 1

32

3 1
1 1
2 1
1 2 100 1

18

В первом тесте из примера карта дорог выглядит так, как показано на рисунке. Кружками обозначены города, линиями — дороги, а числа в квадратах около дорог обозначают номера компаний, обслуживающих эти дороги. Цены проездных в этом примере равны c₁ = 3 бурля, c₂ = 5 бурлей. Таким образом, делегаты, едущие из первого города в третий, или обратно, должны купить оба проездных, остальным делегатам нужно проехать только одну дорогу, поэтому им нужно купить только один проездной. Итоговая стоимость проездных равна 2·(3 + 5) + 2·3 + 2·5 = 32 бурлей.

Во втором тесте схема дорог выглядит так же, а компания-владелец только одна. Стоимость проездного равна 3 бурля. Поэтому все 6 делегатов должны купить единственный проездной, и суммарная стоимость 6·3 = 18 бурлей.

Тесты, в которых выполняются дополнительные ограничения 1 ≤ N, K ≤ 100, имеют суммарную стоимость не менее 30 баллов.

Тесты, в которых выполняются дополнительные ограничения 1 ≤ N, K ≤ 1000, имеют суммарную стоимость не менее 50 баллов.

Тесты, в которых выполняются дополнительные ограничения 1 ≤ N, K ≤ 100 000, имеют суммарную стоимость не менее 75 баллов.