Суеверие
Сегодня долгожданный для всех школьников - первый день каникул нового учебного года. Наша главная героиня - Дени - учится в 10 классе. Она хорошо подготовилась к сегодняшнему дню и выяснила, что в центре города находятся n магазинов. Теперь Дени планирует вместе со своими друзьями посетить некоторые из них. В городе есть m пар магазинов (x[i], y[i]), соединенных двусторонними дорогами. Для каждой дороги известно время, которое требуется для перемещения по ней, оно одно и то же для перемещения в обоих направлениях. Никакой магазин не соединен дорогой сам с собой, никакая пара магазинов не соединена более чем одной дорогой.
Дени очень суеверна и одно из ее суеверий заключается в том, что она верит, что время, потраченное на перемещения между магазинами, должно нацело делиться на d. При этом Дени с друзьями не может перемещаться между магазинами слишком долго, её путь должен занимать суммарно не больше k. Как и все девушки, Дени очень любопытна. Она хочет выяснить, сколько существует различных способов начать свой путь в некотором магазине, перемещаться по дорогам между магазинами, и закончить путь в некотором магазине (возможно посещая по пути некоторые магазиныи/или дороги более одного раза). Дени помнит, что у нее есть друг-программист - Вы - и она проситнаписать программу, которая вычислит количество корректных способов перемещаться между магазинами. Дени считает способ корректным, если её время в пути не превышает k и делится на d. Вы немедленно указываете Дени, что количество путей может быть слишком большим, поэтому Дени просит вывести остаток от деления количества путей на число 1,000,000,007.
Входные данные
На первой строке находятся четыре целых числа n (2 ≤ n ≤ 80), m (2 ≤ m ≤ 3160), d и k (2 ≤ d, k ≤ 10^9). На каждой из следующих m строк находятся по три целых числа x[i], y[i] и t[i] (1 ≤ t[i] ≤ 10) - они задают двустороннюю дорогу между магазинами x[i] и y[i], перемещение по которой занимает t[i] (1 ≤ i ≤ m).
Выходные данные
Выведите остаток от деления количества искомых путей на 1,000,000,007.