Problem Secretul cifrului


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 19997.

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 19997.

Restrictii:

  • 1 ≤ N ≤ 2000; 2 ≤ K ≤ 1000000000
  • 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

General info

ID: 50

Upload: liviu

Input: cifru.in/cifru.out

Memory limit: 16MB/8MB

Time limit: 0.05s

Author: Stelian Ciurea

Source: OJI 2006 XI-XII: Problema 2

Submissions

Special Submissions