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

Условие

Рассмотрим последовательность a₁, …, a_n. Назовём её k-почтимонотонной, если среди неравенств a₁ ≤ a₂, a₂ ≤ a₃, …, a_n − 1 ≤ a_n ровно k неверных.

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

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

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

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

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

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

Ограничения

1 ≤ k ≤ 100;

1 ≤ m ≤ 26;

1 ≤ b_i ≤ 100;

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

2 2
2 2

1