Fişierul intrare/ieşire:	treegcd.in, treegcd.out	Sursă	ONI 2019, clasele 11-12, ziua 1
Autor	Denis Banu	Adăugată de	Pop Alex-Nicolae •AlexPop28
Timp execuţie pe test	0.15 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

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.

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.

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⁹ + 7 pentru numărul cerut.

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.

Exemplu

Cum se trimit solutii?