h2. Date de intrare

În fişierul $treegcd.in$ se află pe prima linie două numere naturale nenule $N$ şi $M$, separate printr-un spaţiu. Pe fiecare din următoarele $N-1$ linii se află câte două numere naturale nenule $x$ şi $y$, separate printr-un spaţiu, cu semnificaţia că nodurile $x$ şi $y$ sunt adiacente.

În fişierul *treegcd.in* se află pe prima linie două numere naturale nenule $N$ şi $M$, separate printr-un spaţiu. Pe fiecare din următoarele $N-1$ linii se află câte două numere naturale nenule $x$ şi $y$, separate printr-un spaţiu, cu semnificaţia că nodurile $x$ şi $y$ sunt adiacente.

h2. Date de ieşire

În fişierul $treegcd.out$ trebuie să se găsească un singur număr. Acest număr reprezintă în câte moduri se poate atribui fiecărui nod o valoare de la $1$ la $M$, astfel încât pentru oricare două noduri adiacente, valorile asociate să nu fie prime între ele. Deoarece rezultatul poate fi foarte mare, se va afişa restul modulo $(10^9^+7)$ pentru numărul cerut.

În fişierul *treegcd.out* trebuie să se găsească un singur număr. Acest număr reprezintă în câte moduri se poate atribui fiecărui nod o valoare de la $1$ la $M$, astfel încât pentru oricare două noduri adiacente, valorile asociate să nu fie prime între ele. Deoarece rezultatul poate fi foarte mare, se va afişa restul modulo $(10^9^+7)$ pentru numărul cerut.

h2. Restricţii