描述

有$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