Fişierul intrare/ieşire:nr.in, nr.outSursă.campion 2006-2007, Runda 1
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.55 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Nr

Zaharel este un mare pasionat de numere. Astazi, se joaca cu numere de N cifre scrise in baza B. Fie NR=nr0nr1...nrN-1 un astfel de numar in baza B (nr0, nr1 etc. reprezinta cifrele numarului NR scrise de la stanga la dreapta), definim imaginea acestui numar ca fiind numarul I(NR)=i0i1...iN-2 cu proprietatea ip=min(ip,ip+1). Avand o groaza de timp liber, Zaharel s-a gandit sa calculeze pentru fiecare numar posibil de N cifre (numarul poate incepe cu cifre de 0) in baza B produsul cifrelor imaginii numarului si sa adune aceste valori.
Scrieti un program care il scuteste pe Zaharel de aceste calcule, si determina aceasta suma in timp util.

Date de intrare

Pe prima linie a fisierului de intrare numere.in sunt scrise cele doua numere naturale N, B, separate printr-un singur spatiu.

Date de iesire

Prima linie a fisierului numere.out va contine suma dorita de Zaharel. Deoarece rezultatul poate fi foarte mare, este de ajuns afisarea restului impartirii rezultatului la numarul 666013.

Restrictii

  • 2 ≤ N ≤ 20.000
  • 2 ≤ B ≤ 1.000

Exemplu

nr.innr.out
2 4
14

Explicatie

NR=00, I(NR)=0 se aduna 0
NR=01, I(NR)=0 se aduna 0
NR=02, I(NR)=0 se aduna 0
NR=03, I(NR)=0 se aduna 0
NR=10, I(NR)=0 se aduna 0
NR=11, I(NR)=1 se aduna 1
NR=12, I(NR)=1 se aduna 1
NR=13, I(NR)=1 se aduna 1
NR=20, I(NR)=0 se aduna 0
NR=21, I(NR)=1 se aduna 1
NR=22, I(NR)=2 se aduna 2
NR=23, I(NR)=2 se aduna 2
NR=30, I(NR)=0 se aduna 0
NR=31, I(NR)=1 se aduna 1
NR=32, I(NR)=2 se aduna 2
NR=33, I(NR)=3 se aduna 3

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content