题目描述

有 $1 \times n$ （ $n \le 50$ ）的一个长方形，用 $1 \times 1$ 、 $1 \times 2$ 和 $1 \times 3$ 的骨牌铺满方格，请问有多少种铺法？

例如当 $n=3$ 时为 $1 \times 3$ 的方格。此时用 $1 \times 1$ 、 $1 \times 2$ 和 $1 \times 3$ 的骨牌铺满方格，共有四种铺法。如下图：

输入

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

输出

骨牌的铺法。

样例

3

4

来源

递推