Problem D: A Simple Math Problem

Problem D: A Simple Math Problem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 66  Solved: 15
[Submit] [Status] [Web Board] [Creator:]

Description

PingTou now is thinking about a simple function f(x).The funcion f(x) is a piecewise function.

If x < 10 f(x) = x.

if x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + ...... + a9 * f(x-10);

S(x) = f(1) + f(2) + f(3) + ......+ f(x);

The f(x) will be too large. So the f(x) modulo to m.

And ai (0 <= i <= 9) can only be 0 or 1.

Now, I will give a0~a9 and two positive integers k and m,and could you help PingTou to caculate S(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 postive integers k and m.(k < 2*10^9 , m < 10^5)

In the second line , there are ten integers represent a0 ~ a9.

Output

For each case, out put S(k) % m in one line.

Sample Input Copy

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 Output Copy

90
175