Ardıcıllıq

Verilmiş ardıcıllıqda başlanğıc qiymətləri a_0, ..., a_{k-1} binominal əmsallardır. Sizdən P = 1000000009 modulu üzrə a_n dəyərini tapmaq tələb olunur.

Giriş verilənləri

Birinci sətirdə boşluqla ayrılmış 2 tam ədəd n və k verilir, burada k ≤ n ≤ 10^18, 1 ≤ k ≤ 200. İkinci sətirdə ardıcıllığın başlanğıc qiymətləri olan k ədəd a_0, a_1, ..., a_{k-1} verilir (0 ≤ a_i < P).

Çıxış verilənləri

Bir tam ədəd çıxarın — P moduluna görə cavab.

Nümunələr