Sim-4-1 | albine

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

Albinuța Livia vrea să-și deschidă un hotel din flori pentru alte albinuțe. Hotelul va fi compus din NN 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 KK 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 NN și KK, 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 0071 \ 000 \ 000 \ 007.

Date de intrare

Pe prima linie se află două numere naturale, NN și KK, 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 0071 \ 000 \ 000 \ 007.

Restricții și precizări

  • 1N1 000 0001 \leq N \leq 1 \ 000 \ 000
  • 1K1 000 000 0001 \leq K \leq 1 \ 000 \ 000 \ 000
# Punctaj Restricții
1 13 1N,K71 \leq N, K \leq 7
2 21 1N,K4001 \leq N, K \leq 400
3 28 1N,K1 0001 \leq N, K \leq 1 \ 000
4 38 Fără restricții suplimentare

Exemplu

stdin

2 2

stdout

14

Explicație

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