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
* $2 ≤ N ≤ 100$
* $2 ≤ M ≤ 10.000$
* pentru teste în valoare de *4 puncte* avem $N = 2$ şi $M ≤ 1.000$.
* pentru alte teste în valoare de *13 puncte* avem $N ≤ 6$ şi $M ≤ 10$.
* pentru teste în valoare de *40 de puncte* avem $N ≤ 100$ şi $M ≤ 100$.
* pentru alte teste în valoare de *43 de puncte* avem $N ≤ 100$ şi $M ≤ 10.000$.
* pentru teste în valoare de $4$ puncte avem $N = 2$ şi $M ≤ 1.000$.
* pentru alte teste în valoare de $13$ puncte avem $N ≤ 6$ şi $M ≤ 10$.
* pentru teste în valoare de $40$ de puncte avem $N ≤ 100$ şi $M ≤ 100$.
* pentru alte teste în valoare de $43$ de puncte avem $N ≤ 100$ şi $M ≤ 10.000$.
h2. Exemplu
table(example). |_. treegcd.in |_. treegcd.out |_. Explicaţii |
| 2 6
1 4
1 2
| 13
| Perechile de valori asociate nodurilor $1, 2$ sunt:
$(2,2), (2,4), (2,6), (3,3), (3,6), (4,2), (4,4),$
