PIBO - Fibonacci vs Polynomial

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

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

hide comments
2021-09-29 22:44:26 David
Trapped by slow Java again!
2011-11-12 01:16:02 Problem Solver
Oh, yes, sorry for that
2011-11-12 01:07:38 Miguel Oliveira
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)
2011-11-12 00:35:25 Problem Solver
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.