문제
어떤 숫자가 계속해서 증가하는 수열을 우리는 증가 수열이라고 한다. 예를 들어 { 1, 3, 5, 10 }은 증가수열이지만 { 1, 1, 3, 5 }나 { 2, 1, 6, 8 }등은 증가수열이 아니다. 어떠한 수 N, M이 주어질 때 1부터 N까지의 숫자를 사용하여 만들수 있는 수열 중 증가수열이면서 서로 인접한 원소의 차이가 M을 초과하지 않는 수열의 개수를 세는 프로그램을 작성하라.
입력
N, M을 입력받는다. (1≤N≤1,000,000, 1≤M≤100 )
출력
1부터 N까지의 숫자를 사용하여 만들수 있는 수열 중 증가수열이면서 서로 인접한 원소의 차이가 M을 초과하지 않는 수열들의 개수를 출력한다. 만약 정답이 1,000,000,007 이상이면 1,000,000,007로 나눈 나머지를 출력한다.
예제
2 1
3
힌트
로그인해야 코드를 작성할 수 있어요.