PIBO  Fibonacci vs Polynomial
Define a sequence Pib(n) as following
 Pib(0) = 1
 Pib(1) = 1
 otherwise, Pib(n) = Pib(n1) + Pib(n2) + 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 ≤ 10^{9}, 0 ≤ d ≤ 100), d is the degree of polynomial.
The second line contains d+1 integers c_{0},c_{1} … c_{d}, represent the coefficient of the polynomial(Thus P(x) can be written as Σc_{i}x^{i}). 0 ≤ c_{i} ≤ 100 and c_{d} ≠ 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:
20111112 01:16:02
Oh, yes, sorry for that 

Miguel Oliveira:
20111112 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


Problem Solver:
20111112 00:35:25
Hey @Bin Jin

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