Зростаючі підпослідовності
Послідовність p(1), p(2), …, p(N), що складається з чисел 1, 2, … , N, називається перестановкою, якщо всі елементи в послідовності різні.
Перестановка p містить зростаючу підпослідовність з k елементів, якщо існують індекси
1 ≤ i_1 < i_2 < … < i_k ≤ N,
такі, що
p(i_1) < p(i_2) < … < p(i_k).
Якщо перестановка p має зростаючу підпослідовність з B елементів, але не має жодної з B+1 елементів, то число B називається ступенем зростання цієї перестановки.
Вам потрібно створити програму, яка, отримавши число N, обчислює кількість перестановок, ступінь зростання яких дорівнює B. Оскільки кількість таких перестановок може бути дуже великою, необхідно обчислити її залишок від ділення на 1000000000.
Вхідні дані
Вхідний файл складається з одного рядка, що містить два цілі числа N та B (1 ≤ N ≤ 40, 1 ≤ B ≤ 5), розділені одним або кількома пробілами.
Вихідні дані
Вихідний файл повинен містити одне ціле число, яке є залишком від ділення на 1000000000 кількості перестановок, ступінь зростання яких дорівнює B.