cuvinte2

Cuvinte 2

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

Poveste si cerinta...

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$}.
 
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
 
Scrieti un program care pentru valorile {$N$} si {$D$} date determina restul la impartirea cu {$9967$} al numarului maxim de cuvinte pe care le poate avea limba vorbita de ofni.

h2. Date de intrare

Fisierul de intrare $cuvinte2.in$ ...

In fisierul text {$cuvinte2.in$} se dau pe linii diferite valorile {$N$} si {$D$}.

h2. Date de iesire

In fisierul de iesire $cuvinte2.out$ ...

In fisierul text {$cuvinte2.out$} se va scrie rezultatul cerut.

h2. Restrictii

* $... ≤ ... ≤ ...$

* {$1 ≤ N ≤ 1.000.000.000$}
* {$1 ≤ D ≤ 1.000$}
* Pentru {$25%$} din teste {$N ≤ 50$}
* Se considera ca {$0$} este divizibil cu orice numar

h2. Exemplu
table(example). |_. cuvinte2.in |_. cuvinte2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
49
| 3

|
h3. Explicatie

...

Exista {$3$} cuvinte de lungime {$2$}, ale caror coduri sunt divizibile cu {$49$}. Acestea sunt {$aa$}, {$yz$} si {$zy$}. {$aa$} are codul {$0$}, iar {$yz$} si {$zy$} au fiecare codul {$49$}.

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

2730