1 ~ N번 칸까지 계단이 있고, 0번 칸에서 시작하여 N번 칸에 도착하고자 한다. 계단을 한 번에 1칸, 2칸 혹은 3칸씩 오르거나, 1칸 혹은 2칸을 내려갈 수 있다. 단, 모든 계단은 한 번만 밟을 수 있으며, 음수 계단과 N+1 계단은 없다고 가정한다. 예를 들어, 3칸을 오르는 방법은 {+1칸, +1칸, +1칸}, {+1칸, +2칸}, {+2칸, -1칸, +2칸}, {+2칸, +1칸}, {+3칸}으로 총 5가지 경우이다. N번 칸에 올라가는 서로 다른 경우의 수를 출력하는 프로그램을 작성하시오. 

계단의 칸 수(N)를 입력한다.

(단, N은 자연수이며, 1 <= N <= 15의 범위를 갖는다.)

계단을 올라가는 서로 다른 경우의 수를 출력한다.