Secretul Cifrului

cifru

==Include(page="template/taskheader" task_id="cifru")==

== include(page="template/taskheader" task_id="cifru") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| cifru.in | cifru.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="cifru") ==

==Include(page="template/raw")==
 
Secretul cifrului
 
Un criptolog amator isi propune sa construiasca o masina de cifrat care sa cripteze un text alcatuit din exact N simboluri distincte. Cifrarea se realizeaza prin permutarea simbolurilor ce formeaza textul.
 
Criptologul nostru doreste ca reconstituirea textului initial sa poata fi realizata trecand textul cifrat inca de K-1 ori prin procedura de cifrare. Cu alte cuvinte, daca textul rezultat din prima cifrare este cifrat inca o data, rezultatul este cifrat din nou si asa mai departe, plecand de la textul initial si aplicand in total K operatii de cifrare successive, trebuie sa obtina textul initial.
 
Criptologul nostru ar vrea sa afle, cunoscand N si K, numarul de moduri distincte in care poate fi realizata masina de cifrat. Doua moduri de realizare a masinii difera daca, exista cel putin un text in urma cifrarii caruia, in cele doua texte obtinute exista cel putin o pozitie in care se afla simboluri diferite.
 
h2. Cerinta
 
Scrieti un program care determina restul impartirii numarului de moduri distincte in care poate fi realizata masina de cifrat la 19997.
 
h2. Date de Intrare
 
Fisierul cifru.in contine pe prima (si singura) linie, doua valori numerice naturale separate printr-un spatiu, N si K (cu semnificatia din enunt)
 
h2. Date de Iesire
 
Fisierul cifru.out va contine pe prima linie, numarul de moduri distincte de realizare a masinii de cifrat modulo 19997.
 
h2. Restrictii
 
 
 
S 1 <= N <= 2000; 2 <= K <= 1000000000
 
S pentru 30% din teste N,K < 13
 
S pentru 50% din teste N,K <= 100
 
 
 
Exemple
 
 
|Exemplul 1: |cifru.in |cifru.out |
|
| |3 3 |3 |
 
|Exemplul 2: |cifru.in |cifru.out |
|
| |9 6 |11560 |
 
|Exemplul 3: |cifru.in |cifru.out |
|
| |100 200 |13767 |
 
==Include(page="template/taskfooter" task_id="cifru")==