Processing math: 100%

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

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

Условие

Рассмотрим последовательность a1, , an. Назовём её k-почтимонотонной, если среди неравенств a1a2, a2a3, , an1an ровно k неверных.

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

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

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

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

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

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

Ограничения

1k100;

1m26;

1bi100;

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

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

0.079s 0.008s 13