SP9964 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.

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.

A single integer represents the answer.