eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 512 MiB

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

План тренировки представляет собой набор целых положительных чисел a[1], a[2], ..., 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[1] + a[2] + ... + a[m] = n. Ограничения на количество дней в плане нет, m может быть любым, но нагрузка в первый день тренировок зафиксирована: a[1] = k.

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

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

Вхідні дані

Два целых числа n и k (1n5000, 1kn).

Вихідні дані

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

Приклад

Вхідні дані #1
6 2
Вихідні дані #1
4
Вхідні дані #2
3 3
Вихідні дані #2
1

Примітка

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

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

Джерело 2018 Всероссийская олимпиада школьников по информатике, Региональный этап, день 2, Москва, 28 января 2019, Задача B