Un criptolog amator îşi propune să construiască o maşină de cifrat care să cripteze un text alcătuit din exact $N$ simboluri distincte. Cifrarea se realizează prin permutarea simbolurilor ce formează textul.

Criptologul nostru doreşte ca reconstituirea textului iniţial sǎ poată fi realizată trecând textul cifrat încă de $K - 1$ ori prin procedura de cifrare. Cu alte cuvinte, dacă textul rezultat din prima cifrare este cifrat încă o data, rezultatul este cifrat din nou şi asa mai departe, plecând de la textul iniţial şi aplicând în total $K$ operaţii de cifrare successive, trebuie să obţină textul iniţial.

Criptologul nostru ar vrea să afle, cunoscând $N$ si $K$, numărul de moduri distincte în care poate fi realizată maşina de cifrat. Două moduri de realizare a maşinii diferă dacă, existǎ cel puţin un text în urma cifrării cǎruia, în cele două texte obţinute există cel puţin o poziţie în care se află simboluri diferite.

Cerinţă

Scrieţi un program care determină restul împǎrţirii numărului de moduri distincte în care poate fi realizată maşina de cifrat la $19\ 997$.

Date de intrare

Fişierul cifru.in conţine pe prima (şi singura) linie, două valori numerice naturale separate printr-un spaţiu, $N$ şi $K$ (cu semnificaţia din enunţ).

Date de ieşire

Fişierul cifru.out va conţine pe prima linie, numǎrul de moduri distincte de realizare a maşinii de cifrat modulo $19\ 997$.

Restricții și precizări

• $1 ≤ N ≤ 2\ 000$
• $2 ≤ K ≤ 1\ 000\ 000\ 000$
• pentru $30\%$ din teste $N, K < 13$
• pentru $50\%$ din teste $N, K ≤ 100$

Exemple

cifru.in

3 3

cifru.out

3

cifru.in

9 6

cifru.out

11560

cifru.in

100 200

cifru.out

13767