Problem
메뚜기는 서로 같은 거리에 있는 같은 줄에 있는 기둥 위로 점프합니다. 열에는 1 에서 N 까지의 일련 번호가 있습니다. 처음에 Grasshopper는 숫자 1이 있는 기둥에 앉아 있습니다. 현재 막대부터 계산하여 1에서 K 막대까지 앞으로 이동할 수 있습니다. Grasshopper가 숫자 N이 있는 열에 도달할 수 있는 방법의 수를 찾는 데 필요합니다. Grasshopper는 뒤로 점프할 수 없습니다.
찾는 방법의 수가 매우 많을 수 있으므로 modulo \(10^6 + 7\) , 즉 이 숫자를 나눗셈의 나머지를 찾으십시오. \(10^6 + 7\) .
입력: 입력 문자열에는 공백으로 구분된 자연수 N 및 K가 포함됩니다. \(1 <= N ,\ K <= 10000\)임을 보장합니다.
출력: 프로그램은 단일 숫자를 인쇄해야 합니다. Grasshopper가 계산된 N 열에 도달할 수 있는 방법의 수입니다. \(10^6+7\) 모듈에서.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
10 5 |
236 |
| 2 |
100 50 |
934384 |