문제1528--증가 수열

1528: 증가 수열

실행시간 제한: 3 Sec  메모리사용 제한: 128 MB
제출: 82  통과: 31
[제출] [채점기록] [묻고답하기]

문제 설명

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

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

입력 설명

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

출력 설명

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

입력 예시 Copy

2 1
4 2
0 0

출력 예시 Copy

3
14

도움

( 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가지이다.

출처/분류