Возрастающие подпоследовательности
Последовательность 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.