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

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

Date de intrare

Se dă $N$ și $K$.

Date de ieșire

Suma cerută modulo $10^9+7$.

Restricții și precizări

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

Exemplul 1

stdin

3 2

stdout

12

Explicație

Toți arborii Cracked cu $3$ noduri sunt:

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

Exemplul 2

stdin

69 420

stdout

50524947