Zaharel este un mare pasionat de numere. Astazi, se joaca cu numere
de N cifre scrise in baza B. Fie NR=x0x1...xN-1 un astfel de numar in baza B
(x0,x1 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(xp,xp+1). Avand o groaza de timp liber, Zaharel
s-a gandit sa calculeze pentru fiecare numar posibil de N cifre in baza B produsul
cifrelor imaginii numarului si sa adune aceste valori.
Cerinta
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 numere3.in sunt scrise cele doua
numere naturale N, B, separate printr-un singur spatiu.
Date
de iesire
Prima linie a fisierului numere3.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 <= 20000
2 <= B <= 1000 Numerele pot incepe cu cifre de 0.
Exemple
numere3.in
numere3.out
Explicatie
2 4
14
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
Mircea Paşoi Universitatea Bucuresti, Facultatea
de Matematica si Informatica bogdanpasoi@yahoo.com