B18 实践-2 骨牌问题2

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

输入格式

一行，一个整数 $n$ ，表示方格数。

输出格式

一行，一个整数，表示方法总数。

样例输入

3

样例输出

4

数据范围

对于 $100\%$ 的数据， $1\le n\le40$。