骨牌铺法(domino)

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

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

输入

输入n（n为自然数，并且1≤n≤36）

输出

输出骨牌铺法的方案数。

【输入样例】

3

【输出样例】

4