Zăhărel şi-a făcut o listă cu toate numerele de L cifre scrise în baza B pentru care suma cifrelor dă restul M când este împărţită la N. Pentru a verifica dacă lista este completă, Zaharel va transforma fiecare astfel de număr în baza 10 şi va face suma tuturor. Apoi va verifica suma cu cea obţinută cu un program rulat pe calculator.
Cerinţă
Scrieţi un program care determină numerele de L cifre scrise în baza B, numere pentru care suma cifrelor dă restul M la împărţirea cu N, le transformă în baza 10, apoi determină suma lor. Deoarece suma numerelor poate fi foarte mare se va afişa restul împărţirii sumei la P.
Date de intrare
Pe prima linie a fişierului de intrare nr2.in sunt scrise numerele naturale L B N M P, în această ordine, separate prin spaţii.
Date de ieşire
Prima linie a fişierului nr2.out va conţine o singură linie pe care va fi scris un număr natural reprezentând suma determinată modulo P.
Restricţii
1 ≤ L ≤ 1016
0 ≤ M < N ≤ 60
2 ≤ B ≤ 10 000
2 ≤ P ≤ 1 000
Exemple
nr2.in
nr2.out
Explicaţii
2 3 2 0 1000
18
Numerele de 2 cifre scrise în baza 3 pentru care suma cifrelor dă restul 0 când este împărţită la 2 sunt 11, 20, 22.
Transformând aceste numere în baza 10 obţinem 4+6+8=18.