19903번 - Интервальные тренировки 서브태스크다국어

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

План тренировки представляет собой набор целых положительных чисел 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.

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

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

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

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