Remote Training on Programming

Рассмотрим последовательность 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 раз.

Ответ требуется вывести по модулю 1 000 000 009.