징검다리 뒤로 건너기

$1$번부터 $N$번까지 번호가 붙은 $N$개의 돌이 순서대로 일렬로 나열되어 있습니다. $1$번 돌에서 출발하여 $N$번 돌까지 주어진 정수 $K$에 대해 다음 규칙을 만족하면서 이동하려 합니다.

• $i$번 돌에서는 $1\le x\le K$인 정수 $x$에 대해 $i+x$번 돌로 이동하거나, $i-1$번 돌로 이동할 수 있습니다.
• 돌이 없는 위치로는 이동할 수 없습니다.
• 출발점과 도착점을 포함하여, 이미 밟은 돌은 다시 밟을 수 없습니다.

규칙에 따라 $1$번 돌에서 $N$번 돌까지 이동하는 경우의 수를 소수 $1\, 000\, 000\, 007(=10^9+7)$로 나눈 나머지를 구해봅시다. 밟은 돌의 번호를 순서대로 나열한 수열이 다르면 다른 이동으로 생각합니다.

첫 번째 줄에 돌의 개수 $N$과 문제의 정수 $K$가 공백으로 구분되어 주어집니다. ($1\le N\le 2\, 000$; $1\le K\le 50$)

첫 번째 줄에 규칙에 따라 $1$번 돌에서 $N$번 돌까지 이동하는 경우의 수를 $1\, 000\, 000\, 007(=10^9+7)$로 나눈 나머지를 출력합니다.