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 before this task, it has lower constraints.

Input

First line of input contains two integer n and d (0 ≤ n ≤ 10⁹, 0 ≤ d ≤ 10000), 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 < 1,111,111,111 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