선물

카레브는 길이가 $K$ 이하인 단순 수열을 아주 좋아한다. 길이가 $L$인 단순 수열은 $0$부터 $L-1$까지의 수를 이 순서대로 나열한 수열이다. 예를 들어 $\{0\}$, $\{0,1,2,3\}$, $\{0,1,2,3,4,5,6\}$은 단순 수열이지만 $\{1\}$, $\{0,1,3,2\}$, $\{0,1,3\}$은 단순 수열이 아니다.

카레브의 생일이 다가와서 폴리는 단순 수열을 몇 개 사서 이어 붙인 흥미로운 수열을 선물하려고 한다. 흥미로운 수열은 길이가 각각 $K$ 이하인 단순 수열 여러 개를 차례로 이어 붙여 만든 수열이다. 예를 들어 $K=3$이면 $\{0,1,2,0\}$, $\{0,1,0,1\}$, $\{0,0,0\}$, $\{0,1,2\}$는 흥미로운 수열이지만 $\{0,1,2,3\}$, $\{0,1,1\}$, $\{0,0,2\}$는 아니다.

고를 수 있는 수열이 워낙 많아서 폴리는 어떤 것을 살지 정하지 못하고 있다. 그래서 선택지가 정확히 몇 가지인지 궁금해졌다.

폴리가 살 수 있는 단순 수열의 최대 길이 $K$와 폴리가 만들려는 흥미로운 수열의 길이 $N$이 주어질 때, 서로 다른 흥미로운 수열이 몇 개인지 구하는 프로그램을 작성한다. 이 수가 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 순서대로 주어진다.

첫째 줄에 폴리가 만들 수 있는 서로 다른 흥미로운 수열의 개수를 $10^9+7$로 나눈 나머지를 출력한다.

• $1 \le K \le N \le 2 \times 10^6$

$N=4$, $K=3$인 경우 가능한 흥미로운 수열은 $\{0,0,0,0\}$, $\{0,0,0,1\}$, $\{0,0,1,0\}$, $\{0,0,1,2\}$, $\{0,1,0,0\}$, $\{0,1,0,1\}$, $\{0,1,2,0\}$의 7개이다.