== include(page="template/taskheader" task_id="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~1~, X2, .., Xp, p >= 2, astfel incat exista strada de la X1 la X2, de la X2 la X3, .. , de la Xp-1 la Xp, iar costul unei astfel de excursii este cel mai mare divizor comun dintre (K, costul strazii de la X1 la X2, costul strazii de la X2 la X3, .. , costul strazii de la Xp-1 la Xp). Deoarece studentii nu au multi bani, acestia vor sa faca excursii cu costul egal cu 1.

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{~1~}, X2, .., Xp, p >= 2, astfel incat exista strada de la X1 la X2, de la X2 la X3, .. , de la Xp-1 la Xp, iar costul unei astfel de excursii este cel mai mare divizor comun dintre (K, costul strazii de la X1 la X2, costul strazii de la X2 la X3, .. , costul strazii de la Xp-1 la Xp). 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