Забобон#8559
Сьогодні довгоочікуваний для всіх школярів день — перший день канікул нового навчального року. Наша головна героїня, Дені, навчається в 10 класі. Вона добре підготувалася до цього дня і дізналася, що в центрі міста є магазинів. Тепер Дені планує разом зі своїми друзями відвідати деякі з них. У місті є пар магазинів (x_i, y_i), з'єднаних двосторонніми дорогами. Для кожної дороги відомо час, необхідний для переміщення по ній, і він однаковий в обох напрямках. Жоден магазин не з'єднаний дорогою сам із собою, і жодна пара магазинів не з'єднана більше ніж однією дорогою.
Дені дуже забобонна, і одне з її забобонів полягає в тому, що час, витрачений на переміщення між магазинами, повинен ділитися націло на . При цьому Дені з друзями не може переміщатися між магазинами занадто довго, її шлях повинен займати сумарно не більше . Як і всі дівчата, Дені дуже цікава. Вона хоче з'ясувати, скільки існує різних способів почати свій шлях у деякому магазині, переміщатися по дорогах між магазинами, і закінчити шлях у деякому магазині (можливо, відвідуючи по дорозі деякі магазини і/або дороги більше одного разу). Дені пам'ятає, що у неї є друг-програміст — Ви — і вона просить написати програму, яка обчислить кількість коректних способів переміщатися між магазинами. Дені вважає спосіб коректним, якщо її час у дорозі не перевищує і ділиться на . Ви негайно вказуєте Дені, що кількість шляхів може бути занадто великою, тому Дені просить вивести залишок від ділення кількості шляхів на число 1\,000\,000\,007.
На першому рядку знаходяться чотири цілі числа (2 \le n \le 80), (2 \le m \le 3160), і (2 \le d, k \le 10^9). На кожному з наступних рядків знаходяться по три цілі числа x_i, y_i і t_i (1 \le t_i \le 10) — вони задають двосторонню дорогу між магазинами x_i і y_i, переміщення по якій займає t_i (1 \le i \le m).
Виведіть залишок від ділення кількості шуканих шляхів на 1\,000\,000\,007.
Приклад 1
Приклад 2
Приклад 3