题目描述

有 $1×n$（n $\leq$ 50）的一个长方形，用一个 $1×1$、$1×2$ 和 $1×3$ 的骨牌铺满方格，请问有多少种铺法？ 例如当 n=3 时为 $1×3$ 的方格。此时用 $1×1$、$1×2$ 和 $1×3$ 的骨牌铺满方格，共有四种铺法。如下图：

输入格式

一个整数 n（n $\leq$ 50）

输出格式

骨牌的铺法

样例

3

4