#1469 격자 채우기

1 s   128 MB  

Description

1 * n 격자에서

1 * 1, 1 * 2, 1 * 3 격자를 이용해서 채우는 방법의 경우의 수

Input

30 이하의 자연수 n 이 주어지며, 입력의 끝은 0

Output

해당 경우의 수를 출력한다.

Sample Input

Sample Output

1
2
3
0
1
2
4

Source

ZJCM