骨牌铺方格III

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

请在1×n的一个长方形方格中,任选1×1、1*2和1*3的骨牌铺满方格,

输入n,输出铺放方案的总数.

例如n=3时,为1*3的方格,骨牌的铺放方案有4种

Input

多组输入,输入到EOF结束,每行包含一个整数n,表示该测试实例的长方形方格的规格是1×n (0< n<=30)。

Output

对于每个测试实例,请输出铺放方案的总数,每个实例的输出占一行。

Sample Input

1
2
3
4

Sample Output

1
2
4 
7

Hint

Source

【2017级《程序设计基础(B)II》期末上机考试补测】玄黄