cifru

Secretul Cifrului

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

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

Poveste ...

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

...

* $1 ≤ N ≤ 2000$
* $2 ≤ K ≤ 1000000000$
* pentru $30%$ din teste $N,K < 13$
* pentru $50%$ din teste $N,K &le; 100$

h2. Date de intrare
...
h2. Date de iesire

Exemple

...
h2. Exemplu

table(example). |_. cifru.in |_. cifru.out |
| 3 3
| 3 |
| 9 6
| 11560 |
| 100 200
| 13767 |

| cifru.in | cifru.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="cifru") ==

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

1008