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


hide comments
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


Added by:Bin Jin
Date:2011-11-11
Time limit:1s
Source limit:10240B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CPP