TreeGCD

treegcd

== include(page="template/taskheader" task_id="treegcd") ==

Când era în vizită la bunici, Cătălin a descoperit în garaj o consolă Nintendo din anul $1970$. Din fericire, această consolă avea şi un joc. Acest joc se chema $“TreeGCD”$. Cătălin primeşte un arbore cu $N$ noduri şi un număr $M$. El trebuie să spună în câte moduri poate să atribuie fiecărui nod un număr de la $1$ la $M$, astfel încât oricare două noduri adiacente să *nu* aibă atribuite numere prime între ele (adică cel mai mare divizor comun este strict mai mare ca $1$).
 
h2. Cerinţă
 
Determinaţi care este numărul de moduri în care putem atribui fiecărui nod câte un număr de la $1$ la $M$, astfel încât oricare două noduri care sunt legate printr-o muchie să nu aibă atribuite numere prime între ele. Numărul trebuie afişat modulo $1.000.000.007$.

Poveste şi cerinţă...

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.

Fişierul de intrare $treegcd.in$ ...

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 de ieşire $treegcd.out$ ...

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$.

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. treegcd.in |_. treegcd.out |_. Explicaţii |
| 2 6
  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),$
$(4,6), (5,5), (6,2), (6,3), (6,4), (6,6).$ |
| 5 6
  5 3
  3 1
  5 4
  3 2
| 397
| Rezultatul este $397$. |
| 10 67
  1 2
  1 3
  2 4
  2 5
  2 6
  2 7
  5 8
  5 9
  7 10
| 534323877
| Rezultatul este $6315455578532062$, iar
$6315455578532062 % 1000000007 = 534323877$ |

table(example). |_. treegcd.in |_. treegcd.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
...

== include(page="template/taskfooter" task_id="treegcd") ==