Задача №114043. Интервальные тренировки
В академии физической культуры разработали новый метод интервальных тренировок спортсменов. В соответствии с этим методом спортсмен должен тренироваться каждый день, однако рост нагрузки должен постоянно сменяться её снижением и наоборот.
План тренировки представляет собой набор целых положительных чисел \(a_1, a_2, \ldots, a_m\), где \(a_i\) описывает нагрузку спортсмена в \(i\)-й день. Любые два соседних дня должны иметь различную нагрузку: \(a_i \ne a_{i + 1}\). Чтобы рост нагрузки и её снижение чередовались, для \(i\) от 1 до \(m - 2\) должно выполняться следующее условие: если \(a_i \lt a_{i + 1}\), то \(a_{i + 1} \gt a_{i + 2}\), если же \(a_i \gt a_{i + 1}\), то \(a_{i + 1} \lt a_{i + 2}\).
Суммарная нагрузка в процессе выполнения плана должна составлять \(n\), то есть \(a_1 + a_2 + \ldots + a_m = n\). Ограничения на количество дней в плане нет, \(m\) может быть любым, но нагрузка в первый день тренировок зафиксирована: \(a_1 = k\).
Прежде чем приступить к тестированию нового метода, руководство академии хочет выяснить, сколько различных планов тренировок удовлетворяет описанным ограничениям.
Требуется написать программу, которая по заданным \(n\) и \(k\) определяет, сколько различных планов тренировок удовлетворяют описанным ограничениям, и выводит остаток от деления количества таких планов на число \(10^9 + 7\).
В первой строке входных данных находятся целые числа \(n\), \(k\) (\(1 \le n \le 5000\), \(1 \le k \le n\)).
Выведите одно число: остаток от деления количества планов тренировок на \(10^9 + 7\).
В первом примере подходят следующие планы: \([2, 1, 2, 1]\), \([2, 1, 3]\), \([2, 3, 1]\), \([2, 4]\).
Во втором примере единственный подходящий план \([3]\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
6 2
4
3 3
1