Коровий картинг
Бесси и фермер Джон наслаждаются гонками на козлах. Идея очень похожа на гонки Go-Kart, которые нравятся другим, за исключением того, что тележки тянут козы, а трасса сделана из близлежащих сельскохозяйственных угодий. Угодья состоят из n лугов и m дорог, каждая из которых соединяет пару лугов.
Бесси хочет построить круговой трек на близлежащих фермах. Ферма - это подмножество двух или более лугов, где с каждого луга можно добраться до любого другого используя уникальную последовательность дорог.
На близлежащих сельскохозяйственных угодьях может находиться несколько ферм. Допустим, уже имеется k ферм. Бесси хотела бы сделать круг для картинга, соединив все k ферм, добавив k дорог длины x. Каждую ферму следует посетить ровно один раз, и внутри каждой фермы необходимо пройти хотя бы по одной дороге.
Чтобы трасса была интересной для гонщиков, ее общая длина должна быть не менее y. Бесси хочет знать сумму длин всех таких интересных трасс. Одна трасса отличается от другой, если на одной трассе есть два соседних луга (после добавления дорог между фермами), но нет на другой. Обратите внимание, что имеют значение только выбранные дороги, а не направление, в котором по ним будут двигаться козлы.
Входные данные
Первая строка содержит числа n, m, x и y (1 ≤ n ≤ 1500, 1 ≤ m ≤ n − 1, 0 ≤ x, y ≤ 2500). Каждая из m следующих строк описывает дороги. Строки имеют вид a[i] b[i] d[i], означающие что луга a[i] и b[i] соединены дорогой целочисленной длины d[i] (1 ≤ a[i], b[i] ≤ n, 0 ≤ d[i] ≤ 2500). Каждый луг примыкает хотя бы к одной дороге, и среди дорог нет циклов.
Выходные данные
Выведите одно целое число - сумму длин всех интересных трасс. Поскольку сумма длин треков может быть довольно большой, выведите сумму их длин по модулю 10^9 + 7.
Пример
В этом примере 6 возможных треков
1 --> 2 --> 4 --> 5 --> 1 (длина 11)
1 --> 2 --> 5 --> 4 --> 1 (длина 11)
2 --> 3 --> 4 --> 5 --> 2 (длина 12)
2 --> 3 --> 5 --> 4 --> 2 (длина 12)
1 --> 2 --> 3 --> 4 --> 5 --> 1 (длина 15)
1 --> 2 --> 3 --> 5 --> 4 --> 1 (длина 15)
Отмет равен 12 + 12 + 15 + 15 = 54, где складываются только те треки, длина которых не менее 12.