Задача №3002. Пилообразные последовательности - 2
Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k.
Входные данные
Программа получает на вход два натуральных числа n и k, 1≤n≤1000, 1≤k≤1000.
Выходные данные
Необходимо вывести остаток от деления количества искомых последовательностей на 109+7.
Примеры
Входные данные
3 3
Выходные данные
10
Входные данные
30 3
Выходные данные
4356618
Сдать: для сдачи задач необходимо войти в систему