계단 오르기 변형

N개의 계단이 있다. 한 번에 1칸, 2칸 또는 3칸을 오를 수 있다.

단, 이전에 오른 칸 수와 같은 칸 수를 연속해서 오를 수 없다.

N번째 계단까지 도달하는 방법의 수를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 계단의 수 N이 주어진다. (1 <= N <= 100,000)

출력

방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

입출력 예시

입력 1

3

출력 1

3

입력 2

5

출력 2

4