Dla danego wielomianu $W$ oraz zadanej liczby $x$, wyznacz trzy ostatnie cyfry (cyfrę setek, dziesiątek i jedności) wartości wyrażenia $W(x)$.
Task
Napisz program, który:
- wczyta opis wielomianu $W$ oraz liczbę $x$,
- wyznaczy trzy ostatnie cyfry wartości wyrażenia $W(x)$,
- wypisze wynik.
Input
Pierwszy wiersz zawiera dwie liczby całkowite $s$ ($1 \le s \le 20\,000$) oraz $x$ ($-1\,000\,000 \le x \le 1\,000\,000$). Drugi wiersz zawiera $s$ liczb całkowitych $w_1$, $w_2$, ..., $w_s$ ($-1\,000\,000 \le w_k \le 1\,000\,000$), pooddzielanych pojedynczymi odstępami. Liczby te, to kolejne współczynniki wielomianu: $W(x) = w_1x^{s-1} + w_2x^{s-2}+\ldots+w_{s-1}x+w_s$.
Output
Twój program powinien wypisać słowo zbudowane z trzech ostatnich cyfr liczby równej wartości wyrażenia $W(x)$, w kolejności od cyfry setek do cyfry jedności.
Example
Input
3 2 5 6 7
Output
039