4072 - 基础算法-递推算法:骨牌铺法

通过次数

105

提交次数

217

时间限制 : 1 秒
内存限制 : 128 MB

有1×n 的一个长方形,用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时为 1×3 的方格。 此时 用 1×1、1×2 和 1×3 的骨牌铺满方格,共有四种铺法。    (n<=40)

输入

输入1个数字n,表示有1×n 的一个长方形

输出

输出1个数字,表示有几种铺法

样例

输入

1

输出

1

输入

2

输出

2