== include(page="template/taskheader" task_id="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.
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 dintre magazine 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)4, 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.
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șacă 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.
h2. 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~].
Fișierul de intrare $superstition.in$ ...
h2. 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
În fișierul de ieșire $superstition.out$ ...
h2. Restricții
* $2 ≤ N ≤ 80$
* $2 ≤ M ≤ 3160$
* $2 ≤ D ≤ K ≤ 10[^9^]$
* $1 ≤ t[~i~] ≤ 10$
* $1 ≤ i ≤ M$
table(example).
|_. Subtask |_. Punctaj |_. N |_. M |_. D |_. K |_. Alte restricții |
| 1
| 5
| ≤ 5
| ≤ 10
| ≤ 12
| ≤ 12
| Nu există alte restricții
|
| 2
| 30
| ≤ 80
| ≤ 3160
| ≤ 10[^4^]
| ≤ 10[^4^]
| Nu există alte restricții
|
| 3
| 10
| ≤ 20
| ≤ 190
| ≤ 10[^9^]
| ≤ 10[^9^]
| D = K și ∑[^M^][~i = 1~] t[~i~]≤ 200
|
| 4
| 20
| ≤ 20
| ≤ 190
| ≤ 10[^9^]
| ≤ 10[^9^]
| ∑[^M^][~i = 1~] t[~i~]≤ 200
|
| 5
| 15
| ≤ 30
| ≤ 435
| ≤ 10[^9^]
| ≤ 10[^9^]
| D = K
|
| 6
| 20
| ≤ 30
| ≤ 435
| ≤ 10[^9^]
| ≤ 10[^9^]
| Nu există alte restricții
|
Programul tău va obține punctajul pe un subtask dacă toate testele din acel subtask vor fi trecute cu succes.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. superstition.in |_. superstition.out |_. Explicații |
| 3 3 2 2
1 2 1
2 3 2
3 1 1
| 8
| Aici D = K = 2 deci soluțiile sunt doar rute de durată 2.
Acestea sunt:
1 – 2 – 1 2 – 1 – 2 3 – 1 – 3
1 – 3 – 1 2 – 3 3 – 2
2 – 1 – 3 3 – 1 – 2
Observați că străzile și magazinele se pot repeta mai mult de o dată.
|
| 5 7 5 10
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4
| 58
| Pentru D < K soluțiile sunt doar rute de durată 5 sau 10
|
| 5 9 2 20
1 2 1
2 3 2
3 1 1
3 4 1
4 5 2
5 3 1
1 5 1
2 4 1
2 5 1
| 989802661
| Aici răspunsul este foarte mare așa că s-a afișat doar restul la împărțirea cu 1,000,000,007 a
numărului determinat.
|
| 5 7 5000000 5000000
1 3 8
2 5 7
3 4 3
1 4 2
2 3 1
1 5 4
4 5 4
| 598634781
| Aici răspunsul este foarte mare așa că s-a afișat doar restul la împărțirea cu 1,000,000,007 a
numărului determinat.
|
|_. superstition.in |_. superstition.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="superstition") ==
