## PIBO - Fibonacci vs Polynomial

no tags

Define a sequence Pib(n) as following

• Pib(0) = 1
• Pib(1) = 1
• otherwise, Pib(n) = Pib(n-1) + Pib(n-2) + P(n)

Here P is a polynomial.

Given n and P, find Pib(n) modulo 1,111,111,111.

### Input

First line of input contains two integer n and d (0 ≤ n ≤ 109, 0 ≤ d ≤ 100), d is the degree of polynomial.

The second line contains d+1 integers c0,c1cd, represent the coefficient of the polynomial(Thus P(x) can be written as Σcixi). 0 ≤ ci ≤ 100 and cd ≠ 0 unless d = 0.

### Output

A single integer represents the answer.

### Example

```Input:
10 0
0

Output:
89

Input:
10 0
1

Output:
177

Input:
100 1
1 1

Output:
343742333

``` Problem Solver: 2011-11-12 01:16:02 Oh, yes, sorry for that Miguel Oliveira: 2011-11-12 01:07:38 The answer is 89. Note that Pib(n) is not the same as the Fibonacci sequence as Pib(0)=1 while Fib(0)=0 Basically, without the polynomial Pib(n) = Fib(n+1) Problem Solver: 2011-11-12 00:35:25 Hey @Bin Jin Very nice problem, but i have a question shouldn't in first testcase answer be 55 ? Because 89 is 11th fibonacci number and we have given n=10 Not a big difference, just saying. Cheers