该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有$\red{1×n}$的一个长方形，用一个$\red{1×1}$、$\red{1×2}$和$\red{1×3}$的骨牌铺满方格。例如当$\red{n=3}$时为$\red{1×3}$的方格。此时用$\red{1×1}$、$\red{1×2}$和$\red{1×3}$的骨牌铺满方格，共有四种铺法。

如图：

输入格式

输入仅一行，为正整数$\red{N}$($\red{0<=n<=40}$)。

输出格式

输出铺法总数。

样例

输入样例

3

输出样例

4