== include(page="template/taskheader" task_id="nr") ==
Zaharel este un mare pasionat de numere. Astazi, se joaca cu numere de $N$ cifre scrise in baza $B$. Fie @NR=nr~0~nr~1~nr~N-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.
Zaharel este un mare pasionat de numere. Astazi, se joaca cu numere de $N$ cifre scrise in baza $B$. Fie $NR=nr{~0~}nr{~1~}...nr{~N-1~}$ un astfel de numar in baza $B$ ({$nr{~0~}, nr{~1~}$} etc. reprezinta cifrele numarului $NR$ scrise de la stanga la dreapta), definim imaginea acestui numar ca fiind numarul $I(NR)=i{~0~}i{~1~}...i{~N-2~}$ cu proprietatea $i{~p~}=min(i{~p~},i{~p+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.
h2. 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.
h2. 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$.
h2. Restrictii
... ≤ ...
* $2 ≤ N ≤ 20.000$
* $2 ≤ B ≤ 1.000$
h2. Exemplu
table(example). |_. nr.in |_. nr.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 4
| 14
|
h3. 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$
== include(page="template/taskfooter" task_id="nr") ==
