갑도는 어느날 지구력 운동을 위하여 계단을 오르려고 한다. 계단은 총 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칸 짜리 계단을 오르려고 한다.
갑도가 계단을 오르는 경우의 수를 구하는 프로그램을 작성하시오.