Интервальные тренировки
Интервальные тренировки
В академии физической культуры разработали новый метод интервальных тренировок спортсменов. В соответствии с этим методом спортсмен должен тренироваться каждый день, однако рост нагрузки должен постоянно сменяться её снижением и наоборот.
План тренировки представляет собой набор целых положительных чисел a1
, a2
, ..., am
, где ai
описывает нагрузку спортсмена в i-й день. Любые два соседних дня должны иметь различную нагрузку: ai
≠ ai+1
. Чтобы рост нагрузки и её снижение чередовались, для i от 1 до m - 2 должно выполняться следующее условие: если ai
< ai+1
, то ai+1
> ai+2
, если же ai
> ai+1
, то ai+1
< ai+2
.
Суммарная нагрузка в процессе выполнения плана должна составлять n, то есть a1
+ a2
+ ... + am
= n. Ограничения на количество дней в плане нет, m может быть любым, но нагрузка в первый день тренировок зафиксирована: a1
= k.
Прежде чем приступить к тестированию нового метода, руководство академии хочет выяснить, сколько различных планов тренировок удовлетворяет описанным ограничениям.
Напишите программу, которая по заданным n и k определяет, сколько различных планов тренировок удовлетворяют описанным ограничениям, и выводит остаток от деления количества таких планов на число 109
+ 7.
Входные данные
Два целых числа n и k (1 ≤ n ≤ 5000, 1 ≤ k ≤ n).
Выходные данные
Выведите одно число: остаток от деления количества планов тренировок на 109
+ 7.
Пояснение
В первом примере подходят следующие планы: [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [2, 4].
Во втором примере единственный подходящий план [3].
6 2
4
3 3
1