eolymp
bolt
Try our new interface for solving problems
Problems

Последовательность

Последовательность

Time limit 1 second
Memory limit 256 MiB

Дана последовательность

с начальными значениями a_0, ..., a_{k-1}, — биномиальные коэффициенты. Требуется найти a_n по модулю P = 1000000009.

Input data

В первой строке содержатся 2 целых числа n и k, разделенных одним пробелом, kn10^18, 1k200. Во второй строке содержатся k чисел a_0, a_1, ..., a_{k-1}, разделенных одним пробелом, — начальные значения последовательности (0a_i < P).

Output data

Выведите одно целое число — ответ по модулю P.

Examples

Input example #1
5 2
1 1
Output example #1
1
Source III International Summer School Programming in Sevastopol 2012