#1528 증가 수열

21  3 s   128 MB  

Description

어떤 숫자가 계속해서 증가하는 수열을 우리는 증가 수열이라고 한다.
예를 들어 { 1, 3, 5, 10 }은 증가수열이지만 { 1, 1, 3, 5 }나 { 2, 1, 6, 8 }등은 증가수열이 아니다.

어떠한 수 N, M이 주어질 때 1부터 N까지의 숫자를 사용하여 만들수 있는 수열 중 증가수열이면서 서로 인접한 원소의 차이가 M을 초과하지 않는 수열의 개수를 세는 프로그램을 작성하라.

Input

N, M을 입력받는다. 만약 N, M이 모두 0이라면 프로그램을 종료한다.
( 1 <= N <= 1,000,000, 1 <= M <= 100 )

Output

매 테스트 케이스마다 1부터 N까지의 숫자를 사용하여 만들수 있는 수열 중 증가수열이면서 서로 인접한 원소의 차이가 M을 초과하지 않는 수열들의 개수를 출력한다.
만약 정답이 1,000,000,007 이상이면 1,000,000,007로 나눈 나머지를 출력한다.

Sample Input

Sample Output

2 1
4 2
0 0
3
14

HINT

( 2, 1 )의 경우
{ 1 }, { 2 }, { 1, 2 } 로 3가지
( 4, 2 )의 경우
{ 1 }, { 2 }, { 3 }, { 4 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, { 2, 4 }, { 3, 4 },
{ 1, 2, 3 }, { 1, 2, 4 }, { 1, 3, 4 }, { 2, 3, 4 }, { 1, 2, 3, 4 }
로 14가지이다.

Source

From Arshuaz