Интервальные тренировки

В академии физической культуры разработали новый метод интервальных тренировок спортсменов. В соответствии с этим методом спортсмен должен тренироваться каждый день, однако рост нагрузки должен постоянно сменяться её снижением и наоборот.

План тренировки представляет собой набор целых положительных чисел a₁, a₂, ... , a_m, где a_i описывает нагрузку спортсмена в i-й день. Любые два соседних дня должны иметь различную нагрузку: a_i ≠ a_i+1. Чтобы рост нагрузки и её снижение чередовались, для i от 1 до m-2 должно выполняться следующее условие: если a_i < a_i+1, то a_i+1 > a_i+2, если же a_i > a_i+1, то a_i+1 < a_i+2.

Суммарная нагрузка в процессе выполнения плана должна составлять n, то есть a₁ + a₂ + ... + a_m = n. Ограничения на количество дней в плане нет, m может быть любым, но нагрузка в первый день тренировок зафиксирована: a₁ = k.

Прежде чем приступить к тестированию нового метода, руководство академии хочет выяснить, сколько различных планов тренировок удовлетворяет описанным ограничениям.

Требуется написать программу, которая по заданным n и k определяет, сколько различных планов тренировок удовлетворяют описанным ограничениям, и выводит остаток от деления количества таких планов на число 10⁹+7.

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

В первой строке входного файла INPUT.TXT находятся целые числа n и k (1 ⩽ n ⩽ 5000, 1 ⩽ k ⩽ n).

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

В выходной файл OUTPUT.TXT выведите одно число: остаток от деления количества планов тренировок на 10⁹+7.

Примеры

Пояснения к примерам

В первом примере подходят следующие планы: [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [2, 4].

Во втором примере единственный подходящий план [3].

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]