문제 설명
계단은 모두 \(n\)칸으로 구성되어 있다. 한 번에 \(1\)칸, \(2\)칸, \(3\)칸을 오를 수 있다. \(m\)번째 계단은 공사 중이다. 따라서 수지는 해당 계단을 사용할 수 없다. 수지가 \(0\)번째 칸에서 출발하여 \(n\)번째 칸으로 오르는 서로 다른 방법의 수를 구해보자. 출력은 1,000,000,007로 나눈 나머지를 출력한다.
입력 설명
정수 \(n, m\)이 입력된다.
\(1 \le m < n \le 1,000,000\)
\(1 \le m < n \le 1,000,000\)
출력 설명
서로 다른 경우의 수의 개수를 1,000,000,007로 나눈 나머지를 출력한다.
입력 예시 Copy
3 2
출력 예시 Copy
2