Problem N: 25-递推-骨牌铺法

Problem N: 25-递推-骨牌铺法

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Submit] [Status] [Web Board] [Creator:]

Description

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



Input

输入一个自然数n(1<n<90)

Output

输出一共有几种铺法

Sample Input

3

Sample Output

4

[Submit][Status]