Se considera un alfabet cu K litere. O parola (sir de litere din acest alfabet) se numeste speciala daca nu exista nicio secventa nevida si strict mai scurta decat parola intreaga care sa apara atat la inceputul parolei, cat si la finalul ei (adica parola nu are niciun "border": niciun prefix propriu nevid nu este egal cu un sufix propriu nevid).
De exemplu, pentru alfabetul {a,e,i,o,u}, parola "aeiio" este speciala, dar "uueiuu" nu este speciala, deoarece secventa "uu" apare atat la inceput cat si la final.
Cerinta: pentru un alfabet cu K litere si o lungime N data, determinati cate parole speciale de lungime N pot fi formate.
- Date de intrare
- Se citesc, pe o singura linie, doua numere naturale K si N.
- Date de iesire
- Se afiseaza numarul de parole speciale de lungime N peste un alfabet cu K litere.
- Restrictii
- 2 <= K <= 10 1 <= N <= 18 (se garanteaza ca rezultatele intermediare incap in intregi pe 64 de biti)
Exemple
Exemplul 1
Intrare
5 10
Iesire
7423100
Exemplul 2
Intrare
2 4
Iesire
6