Задача №3002. Пилообразные последовательности - 210101010101010101010

Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k.

Входные данные

Программа получает на вход два натуральных числа n и k,  1≤n≤1000, 1≤k≤1000.

Выходные данные

Необходимо вывести остаток от деления количества искомых последовательностей на 109+7.

Примеры
Входные данные
3 3
Выходные данные
10
Входные данные
30 3
Выходные данные
4356618
Сдать: для сдачи задач необходимо войти в систему