10985: HDU1757 - A Simple Math Problem
[Creator : ]
Description
Lele now is thinking about a simple function $f(x)$.
If $x < 10\ f(x) = x$.
If $x \ge 10,\ f(x) = a_0 * f(x-1) + a_1 * f(x-2) + a_2 * f(x-3) + \cdots + a_9 * f(x-10)$;
And $a_i\ (0\leq i\leq 9)$ can only be $0$ or $1$ .
Now, I will give $a_0 \sim a_9$ and two positive integers $k$ and $m$, and could you help Lele to caculate f(k)%m.
If $x < 10\ f(x) = x$.
If $x \ge 10,\ f(x) = a_0 * f(x-1) + a_1 * f(x-2) + a_2 * f(x-3) + \cdots + a_9 * f(x-10)$;
And $a_i\ (0\leq i\leq 9)$ can only be $0$ or $1$ .
Now, I will give $a_0 \sim a_9$ and two positive integers $k$ and $m$, and could you help Lele to caculate f(k)%m.
Input
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers $k, m\ ( k<2*10^9,\ m < 10^5)$
In the second line , there are ten integers represent $a_0 \sim a_9$.
In each case, there will be two lines.
In the first line , there are two positive integers $k, m\ ( k<2*10^9,\ m < 10^5)$
In the second line , there are ten integers represent $a_0 \sim a_9$.
Output
For each case, output f(k) % m in one line.
Sample 1 Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
Sample 1 Output
45
104