4072 - 基础算法-递推算法：骨牌铺法
Time Limit : 1 秒
Memory Limit : 128 MB
有1×n 的一个长方形，用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时为 1×3 的方格。 此时 用 1×1、1×2 和 1×3 的骨牌铺满方格，共有四种铺法。 （n<=40）
Input
输入1个数字n,表示有1×n 的一个长方形
Output
输出1个数字，表示有几种铺法
Examples
Input
1
Output
1
Input
2
Output
2