Sequence#3706
Given a sequence defined by the following recurrence relations:
with initial values a_0, ..., a_{k-1}, which are binomial coefficients, your task is to determine a_n modulo P = 1000000009.
The first line contains two integers, and , separated by a space, where k \le n \le 10^{18} and 1 \le k \le 200. The second line provides integers a_0, a_1, ..., a_{k-1}, separated by spaces, representing the initial values of the sequence (0 \le a_i < P).
Output a single integer, which is the value of a_n modulo .
Örnek 1