31004 - 骨牌铺法

有 1×n 的一个长方形,用一个 1×1、1×2 和 1×3 的骨牌铺满方格。例如当 n=3 时为 1×3 的方格。

此时用 1×1、1×2 和 1×3 的骨牌铺满方格,共有四种铺法。如下图:

Input

n

Output

一共有多少种铺法

Examples

Input

3

Output

4
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题