Xurafat

Bu gün bütün məktəblilər üçün çoxdan gözlənilən bir gündür - yeni tədris ilinin ilk tətil günü. Bizim əsas qəhrəmanımız Deni 10-cu sinifdə oxuyur. O, bu günə yaxşı hazırlaşıb və şəhərin mərkəzində n mağaza olduğunu öyrənib. İndi Deni dostları ilə birlikdə bəzi mağazaları ziyarət etməyi planlaşdırır. Şəhərdə m cüt mağaza (x[i], y[i]) var ki, onlar ikitərəfli yollarla birləşir. Hər bir yol üçün həmin yolla hərəkət etmək üçün lazım olan vaxt məlumdur və bu, hər iki istiqamət üçün eynidir. Heç bir mağaza özü ilə yol ilə birləşmir, heç bir mağaza cütü bir yoldan artıq birləşmir.

Deni çox xurafatçıdır və onun xurafatlarından biri odur ki, mağazalar arasında hərəkət etmək üçün sərf olunan vaxt d-yə tam bölünməlidir. Bununla yanaşı, Deni və dostları mağazalar arasında çox uzun müddət hərəkət edə bilməzlər, onun yolu ümumilikdə k-dən çox olmamalıdır. Bütün qızlar kimi, Deni də çox maraqlıdır. O, yoluna hansısa mağazada başlayıb, mağazalar arasında yollardan keçərək, yolunu hansısa mağazada bitirməyin neçə fərqli yolu olduğunu öyrənmək istəyir (yolda bəzi mağazaları və/yaxud yolları bir neçə dəfə ziyarət etmək mümkündür). Deni xatırlayır ki, onun bir proqramçı dostu var - Siz - və o, mağazalar arasında hərəkət etməyin düzgün yollarının sayını hesablayan bir proqram yazmağı xahiş edir. Deni yolu düzgün hesab edir, əgər onun yolda keçirdiyi vaxt k-dən çox deyilsə və d-yə bölünürsə. Siz dərhal Deniyə bildirirsiniz ki, yolların sayı çox böyük ola bilər, buna görə də Deni yolların sayının 1,000,000,007-yə bölünməsindən qalanı çıxarmağı xahiş edir.

Giriş məlumatları

Birinci sətirdə dörd tam ədəd n (2 ≤ n ≤ 80), m (2 ≤ m ≤ 3160), d və k (2 ≤ d, k ≤ 10^9) verilir. Növbəti m sətirdə hər birində üç tam ədəd x[i], y[i] və t[i] (1 ≤ t[i] ≤ 10) var - onlar x[i] və y[i] mağazaları arasında ikitərəfli yolu təyin edir, bu yolla hərəkət etmək t[i] vaxt aparır (1 ≤ i ≤ m).

Çıxış məlumatları

Axtarılan yolların sayının 1,000,000,007-yə bölünməsindən qalanı çıxarın.