Sim-4-1 | albine

Albinuța Livia vrea să-și deschidă un hotel din flori pentru alte albinuțe. Hotelul va fi compus din $N$ flori așezate în linie, fiecare floare reprezentând o cameră de o albină. În timp ce se pregătea pentru deschiderea hotelului, albinuța Livia a decis că ar fi o idee bună să organizeze un weekend de testare în care să-și cheme prietenele să petreacă o noapte într-o parte dintre camerele hotelului.

Albinuța Livia are la dispoziție $K$ culori de flori din care să-și alcătuiască hotelul. Problema este că nu este încă hotărâtă care ar fi cel mai bun design floral și cum să-și distribuie prietenele albinuțe în camere. Singura informație pe care o are este că prietenele ei sunt foarte competitive, deci dacă două dintre ele au aceeași culoare de floare și se pot vedea una pe alta (nicio altă albinuță nu este cazată între ele), cele două vor începe să dezbată pe care dintre ele o prinde mai bine culoarea respectivă și vor pleca acasă nemulțumite. Prin urmare ea vrea neapărat să evite această situație.

Pentru a-și rezolva dilema, albinuța Livia s-a hotărât să deseneze pe o foaie de hârtie toate modurile în care poate alege culorile florilor și să-și repartizeze prietenele în camere. însă, fiind o albinuță foarte practică și grăbită, vă roagă totuși pe voi să o ajutați să calculeze câte astfel de modalități există. Observați că albinuța Livia are un număr variabil de prietene, astfel că voi va trebui să luați în considerare toate variantele.

Cerință

Dându-se $N$ și $K$, numărul de camere și, respectiv, numărul de culori de flori pe care albinuța le are la dispoziție, aflați numărul de moduri posibile modulo $1 \ 000 \ 000 \ 007$.

Date de intrare

Pe prima linie se află două numere naturale, $N$ și $K$, separate printr-un spațiu.

Date de ieșire

Se va afișa un singur număr natural, reprezentând rezultatul modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq K \leq 1 \ 000 \ 000 \ 000$

Exemplu

stdin

2 2

stdout

14

Explicație