1 ~ N번 칸까지 계단이 있고, 0번 칸에서 시작하여 N번 칸에 도착한 후에 다시 0번 칸으로 내려오고자 한다. 올라갈 때는 최대 3칸까지 올라갈 수 있고, 내려올 때는 한 번에 최대 4칸까지 내려올 수 있다. 단, 0번 칸을 제외하고 올라갈 때 밟았던 계단은 내려올 때 밟지 않아야 한다.

예를 들어, N = 2이면, {+1칸, +1칸, -2칸}, {+2칸, -2칸}, {+2칸, -1칸, -1칸}과 같이 3가지 방법이 존재한다. 단, {+1칸, +1칸, -2칸}에서 +1칸은 1칸을 오른다는 의미이고, -2칸은 2칸을 내려간다는 의미이다.

N개의 계단을 올라갔다 내려오는 모든 경우의 수를 구하는 프로그램을 작성하시오.

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

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

N개의 계단을 올라갔다 내려오는 모든 경우의 수를 출력한다.