说明

有1*n的一个长方形方格，用若干个1*1、1*2和1*3的骨牌铺满方格。例如当n=3时，用1*1、1*2和1*3的骨牌铺满方格，共有4钟铺发。

输入格式

输出格式

样例

3

4

提示

对于百分百数据，n (n<=100)