Numere

numere

Zaharel este un mare pasionat de numere. Astazi, se joaca cu numere de N cifre scrise in baza B. Fie NR=x₀x₁...x_N-1 un astfel de numar in baza B (x₀,x₁ etc. reprezinta cifrele numarului NR scrise de la stanga la dreapta), definim imaginea acestui numar ca fiind numarul I(NR)=i₀i₁…i_N-2 cu proprietatea i_p=min(x_p,x_p+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 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 <= 20000
2 <= B <= 1000
Numerele pot incepe cu cifre de 0.

Exemple

numere.in

numere.out

Explicatie

2 4

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

Timp maxim de executie/test: 1.8 secunde

Mircea Paşoi
Universitatea Bucuresti, Facultatea de Matematica si Informatica
bogdanpasoi@yahoo.com