== include(page="template/taskheader" task_id="tenerife") ==
Poveste şi cerinţă...
Un grup de studenti pleaca pe insula Tenerife in vacanta. Acestia vor sa se distreze, dar vor sa cheltuiasca cat mai putini bani. Insula Tenerife este formata din N cluburi si M strazi unidirectionale.
Fiecare strada este data prin X, Y si C, care semnifica ca poti merge din clubul X in clubul Y cu un cost C, dar nu si invers. Deoarece insula e construita astfel incat lumea sa nu se plictiseasca, din orice club ai pleca nu vei putea ajunge inapoi in clubul de pornire mergand pe strazi. O excursie este formata din mai multe cluburi X{~1~}, X{~2~}, ... , X{~p~}, p >= 2, astfel incat exista strada de la X{~1~} la X{~2~}, de la X{~2~} la X{~3~}, ... , de la X{~p-1~} la X{~p~}, iar costul unei astfel de excursii este cel mai mare divizor comun dintre ({*K*}, costul strazii de la X{~1~} la X{~2~}, costul strazii de la X{~2~} la X{~3~}, ... , costul strazii de la X{~p-1~} la X{~p~}). Deoarece studentii nu au multi bani, acestia vor sa faca excursii cu costul egal cu 1.
Ajuta-i pe studenti si calculeaza numarul de excursii diferite care au costul egal cu 1. Deoarece acest numar poate fi foarte mare, trebuie sa il afisati modulo 1000000007.
h2. Date de intrare
Fişierul de intrare $tenerife.in$ ...
Fişierul de intrare $tenerife.in$ contine pe prima linie N, M si K.
Urmeaza M linii, fiecare avand 3 numere, X, Y si C, care semnifica ca exista muchie orientata de la clubul X la clubul Y cu costul C.
h2. Date de ieşire
În fişierul de ieşire $tenerife.out$ ...
În fişierul de ieşire $tenerife.out$ se va afisa numarul de excursii diferite care au costul egal cu $1$ modulo 1000000007.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 1 <= N <= 50.000
* 1 <= M <= 100.000
* 1 <= C, K <= 10^9^
* {*O excursie trebuie sa aiba minim 2 cluburi*}
* Pentru $10%$ din punctaj N <= 1000 si graful va avea forma de lant orientat intr-o singura parte.
* Pentru alte $10%$ din punctaj K = 1.
* Pentru alte $10%$ din punctaj K este numar prim.
* Pentru alte $20%$ din punctaj K <= 5000.
* Pentru alte $50%$ din punctaj restrictiile initiale.
h2. Exemplu
table(example). |_. tenerife.in |_. tenerife.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 7 7 66
1 3 2
2 3 3
3 4 6
3 5 5
5 6 7
4 6 35
7 5 15
| 12 |
| 10 12 840
1 2 2
1 3 10
2 3 6
3 4 15
4 5 10
5 6 25
6 7 35
7 8 50
8 9 20
9 10 49
1 9 42
4 6 200
| 33
|
h3. Explicaţie
...
Pentru primul exemplu:
Excursiile care au costul egal cu 1 sunt:
1) 3 -> 5
2) 5 -> 6
3) 4 -> 6
4) 1 -> 3 -> 5
5) 2 -> 3 -> 5
6) 3 -> 5 -> 6
7) 3 -> 4 -> 6
8) 7 -> 5 -> 6
9) 1 -> 3 -> 4 -> 6
10) 1 -> 3 -> 5 -> 6
11) 2 -> 3 -> 5 -> 6
12) 2 -> 3 -> 4 -> 6
== include(page="template/taskfooter" task_id="tenerife") ==
