Задача G. k-почтимонотонность

Автор:Жюри летних сборов 2009   Ограничение времени:15 сек
Входной файл:kinc.in   Ограничение памяти:256 Мб
Выходной файл:kinc.out  
Максимальный балл:100  

Условие

Рассмотрим последовательность a1, , an. Назовём её k-почтимонотонной, если среди неравенств a1 ≤ a2, a2≤ a3, , an − 1≤ an ровно k неверных.

Даны числа 0 ≤ b1, b2, …, bm ≤ n, где b1 + b2 + …  + bm = n. Найдите количество k-почтимонотонных последовательностей, в которой число 1 встречается b1 раз, 2 встречается b2 раз, , m — bm раз.

Ответ требуется вывести по модулю 109 + 9.

Формат входного файла

В первой строке заданы два натуральных числа k и m. В следующей строке задано m натуральных чисел bi.

Формат выходного файла

Выведите единственное число — ответ на поставленную задачу.

Ограничения

1 ≤ k ≤ 100;

1 ≤ m ≤ 26;

1 ≤ bi ≤ 100;

Примеры тестов

Входной файл (kinc.in) Выходной файл (kinc.out)
1
2 2
2 2
1

0.117s 0.023s 13