SP13940 PIBO2 - Fibonacci vs Polynomial (HARD)

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. Maybe you should solve [PIBO](../PIBO/) before this task, it has lower constraints.

First line of input contains two integer **n** and **d** (0 n d 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} $ < 1,111,111,111 and **c** $ _{d} $ ≠ 0 unless d = 0.

A single integer represents the answer.