아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

인터벌 트레이닝

시간 제한2초메모리 제한512 MB

요약
k로 시작해 합이 n이 되면서 인접한 값의 대소 관계가 위아래로 번갈아 나타나는 양의 정수 수열의 개수를 10^9+7로 나눈 나머지를 구한다.
난이도

보통10점 중 7점

유형
동적 계획법, 조합론, 수학, 누적 합
정답자
아직 제출이 없습니다

문제

체육 대학에서 선수를 위한 새로운 인터벌 트레이닝 방법을 개발했다. 이 방법에 따르면 선수는 매일 훈련해야 하지만, 부하의 증가와 감소가 번갈아 나타나야 한다.

훈련 계획은 양의 정수 수열 a1,a2,…,ama_1, a_2, \ldots, a_m으로 나타내며, aia_i는 ii일째 선수의 부하를 뜻한다. 인접한 두 날의 부하는 서로 달라야 한다: ai≠ai+1a_i \ne a_{i+1}. 부하의 증가와 감소가 번갈아 나타나려면 i=1i = 1부터 m−2m - 2까지 다음 조건을 만족해야 한다: ai<ai+1a_i < a_{i+1}이면 ai+1>ai+2a_{i+1} > a_{i+2}이고, ai>ai+1a_i > a_{i+1}이면 ai+1<ai+2a_{i+1} < a_{i+2}이다.

계획 전체의 부하 합은 nn이어야 한다. 즉 a1+a2+…+am=na_1 + a_2 + \ldots + a_m = n이다. 계획의 일수에는 제한이 없어 mm은 임의로 정할 수 있지만, 첫날의 부하는 고정되어 있다: a1=ka_1 = k.

새 방법을 시험하기 전에 대학 측은 조건을 만족하는 훈련 계획이 몇 가지인지 알아보려 한다. nn과 kk가 주어졌을 때 조건을 만족하는 훈련 계획의 수를 구하고, 그 수를 109+710^9 + 7로 나눈 나머지를 출력하는 프로그램을 작성하라.

입력

첫째 줄에 정수 nn과 kk가 주어진다 (1≤n≤50001 \le n \le 5000, 1≤k≤n1 \le k \le n).

출력

훈련 계획의 수를 109+710^9 + 7로 나눈 나머지를 한 줄에 출력한다.

힌트

첫 번째 예제에서는 다음 계획들이 조건을 만족한다: [2,1,2,1][2, 1, 2, 1], [2,1,3][2, 1, 3], [2,3,1][2, 3, 1], [2,4][2, 4].

두 번째 예제에서는 [3][3]만이 조건을 만족한다.

예제2

  1. 예제 1

    입력
    6 2
    
    예상 출력
    4
    
  2. 예제 2

    입력
    3 3
    
    예상 출력
    1