26526번 - 살얼음판 걷기

문제

대입이 끝나 심심한 즈티는 빙판이 된 한강에 놀러 갔다. 하지만 아직 빙판이 얇아 오래 서 있을 수 없었고, 이대로 돌아가고 싶지 않았던 즈티는 다음과 같은 놀이를 생각해냈다.

한강은 땅 한 칸과 땅과 일자로 이어져 있는 빙판 $N-1$칸으로 모델링할 수 있다. 땅에는 1ドル,ドル 빙판에는 땅과 가까운 순서대로 2ドル$부터 $N$까지 번호를 부여하자. 즈티는 1ドル$번 칸에서 출발하여 $N$번 칸을 밟고 다시 1ドル$번 칸으로 돌아오려고 한다. 이때, 모든 얼음 칸은 한 번 밟으면 녹아 없어져 다시 밟지 못한다.

즈티는 한 걸음에 1ドル$개 이상 $K$개 이하의 칸을 이동할 수 있으며, $N$번 칸을 밟기 전까지는 땅에서 멀어지는 방향, 그 후로는 땅에 가까워지는 방향으로만 이동한다. 임의의 $X$번 칸에서 $Y$번 칸으로 한 걸음에 이동할 때 $X$와 $Y$ 사이에 있는 칸은 밟지 않는다. 1ドル$번 칸과 $N$번 칸 사이를 무사히 왕복하는 경우의 수를 구해 즈티의 놀이를 도와주자.

아래 그림은 $(N, K) = (8, 3)$일 때 가능한 이동 중 하나이다. $(8, 5)$ 등의 예시도 될 수 있다.

입력

첫 번째 줄에 두 정수 $N,ドル $K$가 주어진다. $(1 \leq K < N \leq 3,000円)$

출력

가능한 이동 방법의 수를 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

힌트