# 斐波那契数列 - 持续更新

Posted by WildCow on March 8, 2018

#### 2018-03-08

##### 基本介绍

$Fic(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}]$

#### 2018-03-11



LL quickmod(LL a, LL b, LL MOD)
{
LL ans = 1;
while(b){
if(b & 1){
ans = (ans * a) % MOD;
}
b >>= 1;
a = a * a % MOD;
}

return ans % MOD;
}


HDU - 1757

# A Simple Math Problem

Time Limit: 3000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

### Description

Lele now is thinking about a simple function f(x).

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));
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 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 and m. (( k<2*10^9 , m < 10^5 ))
In the second line , there are ten integers represent a0 ~ a9.

### Output

For each case, output f((k)) % m in one line.

### Sample 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

45
104