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

Arheologii au descoperit de curand ruinele capitalei vechii civilizatii Ofni. Dupa studierea mai multor inscriptii s-au facut urmatoarele observatii cu privire la ortografia limbii vorbite în tara Ofni :

Arheologii au descoperit de curand ruinele capitalei vechii civilizatii Ofni. Dupa studierea mai multor inscriptii s-au facut urmatoarele observatii cu privire la ortografia limbii vorbite in tara Ofni :

* Toate cuvintele erau formate doar din litere mici ale alfabetului englez
* Toate cuvintele aveau acelasi numar de litere, {$N$}

* Daca asociem fiecarei litere un numar de ordine corespunzator pozitiei sale in alfabet ({$0$} pentru {$a$}, {$1$} pentru {$b$}, ..., {$25 $}pentru {$z$}) ai fiecarui cuvant un cod egal cu suma numerelor asociate literelor sale (de exemplu cuvantului {$abc$} ii va corespunde codul {$0+1+2=3$}), atunci toate cuvintele limbii vorbite de Ofni au codul divizibil cu {$D$}.

* Daca asociem fiecarei litere un numar de ordine corespunzator pozitiei sale in alfabet ({$0$} pentru {$a$}, {$1$} pentru {$b$}, ..., {$25$} pentru {$z$}) ai fiecarui cuvant un cod egal cu suma numerelor asociate literelor sale (de exemplu cuvantului {$abc$} ii va corespunde codul {$0+1+2=3$}), atunci toate cuvintele limbii vorbite de Ofni au codul divizibil cu {$D$}.

Dupa ce au stabilit toate aceste reguli, arheologii ar dori sa stie cat de multe cuvinte ar fi putut avea limba vorbita de Ofni. Cum insa nu se pricep prea bine la calcule complicate, va cer ajutorul. Avand în vedere ca numarul cuvintelor poate fi foarte mare, arheologii se multumesc cu restul obtinut la impartirea acestuia la {$9967$}.

Dupa ce au stabilit toate aceste reguli, arheologii ar dori sa stie cat de multe cuvinte ar fi putut avea limba vorbita de Ofni. Cum insa nu se pricep prea bine la calcule complicate, va cer ajutorul. Avand in vedere ca numarul cuvintelor poate fi foarte mare, arheologii se multumesc cu restul obtinut la impartirea acestuia la {$9967$}.

h2. Cerinta

* {$1 ≤ N ≤ 1.000.000.000$}
* {$1 ≤ D ≤ 1.000$}

* Pentru {$50%$} din teste {$N ≤ 50$}

* Pentru {$25%$} din teste {$N ≤ 50$}

* Se considera ca {$0$} este divizibil cu orice numar
h2. Exemplu

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

2730