Cerință
Cu toții știm că un arbore este frumos colorat dacă toate nodurile de aceași culoare sunte accesibile trecând doar prin noduri de culoarea lor.
Se mai cunoaște și că un arbore Cracked e un arbore pentru care tatăl oricărui nod are valoare etichetei mai mică ca valoarea etichetei nodului (Deci e rădăcinat în ).
Fie numărul de colorări frumoase a arborelui cu K culori.
Cât este , unde este un arbore Cracked cu noduri?
Date de intrare
Se dă și .
Date de ieșire
Suma cerută modulo .
Restricții și precizări
- ;
Exemplul 1
stdin
3 2
stdout
12
Explicație
Toți arborii Cracked cu noduri sunt:
Avem culori la dispoziție, pentru primul arbore colorarea:
Nodul culoarea .
Nodul culoarea .
Nodul culaorea .
Este o colorare corectă. Pe când colorarea:
Nodul culoarea .
Nodul culoarea .
Nodul culaorea .
Nu este corectă deoarece nodurile și au aceași culoare iar drumul dintre ele conține si o culoare diferită de .
Exemplul 2
stdin
69 420
stdout
50524947