题目描述

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

当 $n=3$ 时，四种铺法的骨牌长度依次为：1+1+1、1+2、2+1、3。

输入格式

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

输出格式

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

样例输入

3

样例输出

4

数据范围

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

整理说明：原题失效的示意图片已根据原有文字和样例改为文字、公式或表格说明。