징검다리 뒤로 건너기

$1$번부터 $N$번까지 번호가 붙은 $N$개의 돌이 순서대로 일렬로 놓여 있습니다. $1$번 돌에서 출발하여 아래 규칙을 따라 $N$번 돌까지 이동합니다. 정수 $K$가 주어집니다.

• $i$번 돌에서는 $1\le x\le K$인 정수 $x$에 대해 $i+x$번 돌로 이동할 수 있습니다.
• $i$번 돌에서는 $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)$로 나눈 나머지를 출력합니다.