Fişierul intrare/ieşire:	cuvinte2.in, cuvinte2.out	Sursă	OLI 2008, Bucuresti, clasele 11-12
Autor	Victor Manz	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.175 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

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.

Date de intrare

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

Date de iesire

In fisierul text cuvinte2.out se va scrie rezultatul cerut.

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

Exemplu

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.

Cum se trimit solutii?