Problems
Последовательность
Последовательность
Дана последовательность
с начальными значениями a_0, ..., a_{k-1}, — биномиальные коэффициенты. Требуется найти a_n по модулю P = 1000000009.
Input data
В первой строке содержатся 2 целых числа n и k, разделенных одним пробелом, k ≤ n ≤ 10^18, 1 ≤ k ≤ 200. Во второй строке содержатся k чисел a_0, a_1, ..., a_{k-1}, разделенных одним пробелом, — начальные значения последовательности (0 ≤ a_i < P).
Output data
Выведите одно целое число — ответ по модулю P.
Examples
Input example #1
5 2 1 1
Output example #1
1