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 succesive, 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 19997.
Date de intrare
Fişierul cifru2.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 cifru2.out va conţine pe prima linie, numǎrul de moduri distincte de realizare a maşinii de cifrat modulo 19997.
Restricţii
1 ≤ N ≤ 2000; 2 ≤ K ≤ 1000000000
Pentru 30% din teste N, K < 13
Pentru 50% din teste N, K ≤ 100