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