시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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

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

서브태스크

번호 배점 조건
1 23

1 ⩽ n ⩽ 10

2 20

1 ⩽ n ⩽ 30

3 23

1 ⩽ n ⩽ 500

4 34

1 ⩽ n ⩽ 5000

예제 입력 1

6 2

예제 출력 1

4

예제 입력 2

3 3

예제 출력 2

1

힌트

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

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.