Fișierul intrare/ieșire	superstition.in, superstition.out	Sursă	Concurs Shumen seniori 2017
Autor	autor necunoscut	Adăugată de	Spatarel Dan-Constantin • spatarel
Timp de execuție pe test	30 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Superstition

Astăzi este cea mai așteptată zi pentru toți elevii, prima vacanță din noul an școlar. Eroina noastră principală Deni este clasa a X-a. S-a pregătit pentru ziua de azi, a aflat că sunt N magazine în oraș și a plănuit să viziteze unele dintre ele cu prietenii. Anumite străzi nu sunt preferate de Deni și prietenii ei și de aceea nu le vor folosi. Așadar, aceștia au creat o listă de M perechi de magazine de forma (x, y), având semnificația că există o stradă (bidirecțională) acceptată de Deni ce leagă magazinul cu numărul x de magazinul cu numărul y. În plus, pentru fiecare pereche din listă au determinat timpul necesar parcurgerii străzii corespunzătoare (care este acela și pentrutraversarea în ambele direcții). În listă nu există perechi între magazine cu același număr și nici perechi duplicate.

Deni este foarte superstițioasă și una dintre superstițiile în care ea crede este că timpul destinat întregii de plasări trebuie să fie divizibil cu D. Deni și prietenii ei nu au timp nelimitat așa că timpul maxim pe care ei îl pot petrece este K. Ca orice fată, Deni este foarte curioasă și începe să numere câte rute diferite pentru a vizita unele dintre magazine există (un magazin poate fi vizitat de mai multe ori). Din păcate acest număr poate fi foarte mare iar Deni își aduce aminte că te cunoaște pe tine, un foarte bun programator și îți cere să scrii programul care numără câte rute valide există. O rută este validă dacă folosește doar străzi din lista de perechi dată și timpul total de traversare este divizibil cu D și este cel mult K. Două rute se consideră diferite dacă secvențele de magazine vizitate în ordine în cadrul acestora sunt diferite. Îți dai imediat seama că răspunsul poate fi foarte mare, de aceea Deni îțispune că vrea doar restul la împărțirea cu 1 000 000 007 al numărului determinat.

Date de intrare

Fișierul de intrare superstition.in conține patru numere întregi N, M, D și K. De pe următoarele М linii se citesc câte trei numere întregi x_i, y_i și t_i reprezentând strada bidirecțională dintre magazinele x_i și y_i traversată în timpul t_i.

Date de ieșire

Fișierul de ieșire superstition.out va conține numărul de rute diferite valide determinat. De vreme ce numărul poate fi foarte mare, ți se cere să afișezi restul la împărțirea cu 1 000 000 007 al numărului determinat

Restricții

• 2 ≤ N ≤ 80
• 2 ≤ M ≤ 3160
• 2 ≤ D ≤ K ≤ 10⁹
• 1 ≤ t_i ≤ 10
• 1 ≤ i ≤ M

Programul tău va obține punctajul pe un subtask dacă toate testele din acel subtask vor fi trecute cu succes.

Exemplu

Explicație

...