Fişierul intrare/ieşire:	tenerife.in, tenerife.out	Sursă	FMI No Stress 9
Autor	Stelian Chichirim	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.75 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tenerife

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 in acelasi club mergand pe strazi. O excursie este formata din mai multe cluburi X₁, X₂, ... , X_p, p >= 2, astfel incat exista strada de la X₁ la X₂, de la X₂ la X₃, ... , 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₁ la X₂, costul strazii de la X₂ la X₃, ... , 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. 

Date de intrare

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.

Date de ieşire

În fişierul de ieşire tenerife.out se va afisa numarul de excursii diferite care au costul egal cu 1 modulo 1000000007.

Restricţii

• 1 <= N <= 50.000
• 1 <= M <= 100.000
• 1 <= C, K <= 10⁹
• 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 30% din punctaj K <= 10⁴.
• Pentru alte 40% din punctaj restrictiile initiale.

Exemplu

Explicaţie

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

Cum se trimit solutii?