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 ≤ 10⁹, 0 ≤ d ≤ 100), d is the degree of polynomial.

The second line contains d+1 integers c₀, c₁ … c_d, represent the coefficient of the polynomial (Thus P(x) can be written as Σc_ixⁱ). 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