Владения Фермера Джона состоят из \(N\) лугов и \(M\) дорожек, соединяющих пары лугов.
Беси хочет сделать трассу по соседним фермам. Ферма - это подмножество из двух
или более лугов, при том, что каждый луг достижим из любого другого с помощью
уникальной последовательности дорожек.
Farmland может состоять из множества ферм. Пусть имеется \(K\) ферм.
Беси хочет сделать гоночный цикл, соединив \(K\) ферм добавлением \(K\) дорожек
с длиной \(X\). Каждую ферму необходимо посетить ровно раз и пройти как минимум
по одной дороге каждой фермы.
Для того, чтобы сделать трассу более интересной для гонщиков, общая длина
трассы должна быть не менее \(Y\). Беси хочет узнать длины всех подходящих
под эти ограничения трасс. Трасса считается отличающейся от другой, если
есть два соседних луга (после добавления дорожек между фермами) в одной трассе,
которые не являются соседними в другой. Заметим, что имеют значение только
выбранные дорожки, а не направление движения по этим дорожкам.
ФОРМАТ ВВОДА (файл mooriokart.in):
Первая строка ввода содержит
\(N\),
\(M\),
\(X\),
\(Y\) где
\(1 \leq N \leq 1500\),
\(1 \leq M \leq N-1\), and
\(0 \leq X, Y \leq 2500\).
Каждая из последующих \(M\) строк описывает дороги. Строки имеют вид:
\(A_i\) \(B_i\) \(D_i\),
означающие, что луга \(A_i\) и \(B_i\) связаны дорожкой с целое длиной \(D_i\)
(\(1 \leq A_i, B_i \leq N\), \(0 \leq D_i \leq 2500\)).
Каждый луг связан как минимум с одной дорогой, отсутствуют циклы.
В не менее чем 70% тестов гарантируется, что \(N \leq 1000\) и \(Y \leq 1000\).
ФОРМАТ ВЫВОДА (файл mooriokart.out):
Выведите одно целое число, сумму длин всех подходящих трасс по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3 1 12
1 2 3
2 3 4
4 5 6
|
54
|