N. Пилообразная последовательность

Назовём последовательность пилообразной, если каждый её элемент либо строго больше обоих соседей, либо строго меньше обоих. У крайних элементов сосед один, и сравнивать надо только с ним.

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

Памяти немного: полная таблица «длина на значение» сюда не поместится.

Одна строка содержит числа $n$ и $k$ ($1 \le n \le 4000$, $1 \le k \le 4000$).

Одно число — количество пилообразных последовательностей по модулю $10^9 + 7$.