문제 번호 2351 --디룩디룩

2351: 디룩디룩

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 183  해결 문제 수: 19
[제출][채점상황][게시판][:]

문제 설명

갑도는 어느날 지구력 운동을 위하여 계단을 오르려고 한다. 계단은 총 N칸으로 구성되며, 갑도는 한번에 1칸, 2칸, 3칸을 오를 수 있다.

이 경우 총 N칸 짜리 계단을 모두 오르는데 가능한 경우의 수는 a(1)=1, a(2)=2, a(3)= 4, a(n)=a(n-1)+a(n-2)+a(n-3) (n>=4) 로 구할 수 있다.

하지만 갑도는 놀라운 사실을 발견하였다.

계단을 오를 때 1칸을 3번 연속 오르게 되면 이는 지구력 향상에 도움을 주지 않는다는 것이다.

또한 3칸을 3번 연속 오르게 되면 너무 빨리 지쳐서 역시 지구력 향상에 도움을 주지 않는다.

이러한 사실을 토대로 갑도는 1칸을 3번 연속, 또는 3칸을 3번 연속으로 오르지 않도록 하면서 총 N칸 짜리 계단을 오르려고 한다.

갑도가 계단을 오르는 경우의 수를 구하는 프로그램을 작성하시오.

문제출제 : 서울대학교 컴퓨터공학부 오평석

입력

갑도가 오르고자 하는 계단의 총 칸 수 N이 주어진다. (1<=N<=1,000,000)

출력

출력의 첫 줄에 종민이가 계단을 오르는 경우의 수를 1,000,000,007 (10억 7) 로 나눈 나머지를 출력한다.

입력예시

4

출력예시

6

도움말

채점에 사용되는 채점 데이터의 비율은 다음과 같다.


N<=10 : 10%


N<=200 : 20%


N<=5000 : 50%


N<=1000000 : 100%

출처

[제출][채점상황]