Secretul Cifrului

cifru

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

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

==Include(page="template/raw")==
 
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.

Poveste ...

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

Exemple

h2. Date de iesire
...

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

h2. Exemplu
| cifru.in | cifru.out |
| linia1
linia2
linia3
| linia1
linia2
|

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

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