문제

번째 칸부터 번째 칸까지 총 칸이 있는 계단이 있다. 번째 칸은 계단의 시작점이고, 번째 칸은 계단의 꼭대기이다.

태우는 계단의 시작점부터 출발해 계단을 올라 꼭대기에 도달한 후, 다시 시작점으로 내려가는 운동을 하기로 했다. 이때 시작점을 제외한 모든 칸은 정확히 번씩 밟아야 하며, 꼭대기를 제외한 곳에서는 방향을 바꿀 수 없다. 이때, 한 번에 최대 개의 칸만큼 올라가거나 내려갈 수 있다. 엄밀하게 표현하면, 계단의 번째 칸에 있을 때 를 만족하는 계단의 번째 칸으로 이동이 가능하다.

태우가 계단을 오르내리는 운동을 할 때 이동하는 방법의 수를 구하여라.

입력

첫째 줄에 계단의 꼭대기 칸의 번호 과 태우가 한 번에 오르내릴 수 있는 계단의 수 가 공백으로 구분되어 주어진다. ()

출력

가능한 이동 방법의 수를 로 나눈 나머지를 출력한다.

노트

예제 1과 같이 일 때, , , 순서로 이동하는 방법이 있다.