CrackContest | E - Crackul post mijlociu

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 128MB Input: Output:

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

Fie F(X,K)=F(X,K)= numărul de colorări frumoase a arborelui XX cu K culori.
Cât este F(A,K)\sum F(A,K), unde AA este un arbore Cracked cu NN noduri?

Date de intrare

Se dă NN și KK.

Date de ieșire

Suma cerută modulo 109+710^9+7.

Restricții și precizări

  • 1N,K1061 \leq N,K \leq 10^6;

Exemplul 1

stdin

3 2

stdout

12

Explicație

Toți arborii Cracked cu 33 noduri sunt:

Avem 22 culori la dispoziție, pentru primul arbore colorarea:
Nodul 11 culoarea 11.
Nodul 22 culoarea 22.
Nodul 33 culaorea 11.
Este o colorare corectă. Pe când colorarea:
Nodul 11 culoarea 11.
Nodul 22 culoarea 22.
Nodul 33 culaorea 22.
Nu este corectă deoarece nodurile 22 și 33 au aceași culoare iar drumul dintre ele conține si o culoare diferită de 22.

Exemplul 2

stdin

69 420

stdout

50524947

Log in or sign up to be able to send submissions!