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^9+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

treegcd.in

2 6
1 2

treegcd.out

13

Explicații

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

treegcd.in

5 6
5 3
3 1
5 4
3 2

treegcd.out

397

Explicații

Rezultatul este 397.

treegcd.in

10 67
1 2
1 3
2 4
2 5
2 6
2 7
5 8
5 9
7 10

treegcd.out

534323877

Explicații

Rezultatul este 6315455578532062, iar 6315455578532062 % 1000000007 = 534323877.