For a given polynomial $W$ and a given number $x$, determine the last three digits (the hundreds, tens, and units digits) of the value of the expression $W(x)$.
Task
Write a program that:
- reads the description of the polynomial $W$ and the number $x$,
- determines the last three digits of the value of the expression $W(x)$,
- prints the result.
Input
The first line contains two integers $s$ ($1 \le s \le 20\,000$) and $x$ ($-1\,000\,000 \le x \le 1\,000\,000$). The second line contains $s$ integers $w_1, w_2, \ldots, w_s$ ($-1\,000\,000 \le w_k \le 1\,000\,000$), separated by single spaces. These numbers are the successive coefficients of the polynomial: $W(x) = w_1x^{s-1} + w_2x^{s-2}+\ldots+w_{s-1}x+w_s$.
Output
Your program should print a string consisting of the last three digits of the number equal to the value of the expression $W(x)$, in the order from the hundreds digit to the units digit.
Examples
Input 1
3 2 5 6 7
Output 1
039