Автор: | Жюри летних сборов 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 |
|
|