Fişierul intrare/ieşire:	cifru.in, cifru.out	Sursă	OJI 2006
Autor	Stelian Ciurea	Adăugată de
Timp execuţie pe test	0.125 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Secretul Cifrului

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.

Cerinta

Scrieti un program care determina restul impartirii numarului de moduri distincte in care poate fi realizata masina de cifrat la 19997.

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)

Date de Iesire

Fisierul cifru.out va contine pe prima linie, numarul de moduri distincte de realizare a masinii de cifrat modulo 19997.

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 |

Cum se trimit solutii?