== 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~}, 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.

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