题目描述

有 \(1×n\) 的一个长方形，用一个 \(1×1、1×2\) 和 \(1×3\) 的骨牌铺满方格。例如当 \(n=3\) 时为 \(1×3\) 的方格。此时用 \(1×1，1×2\) 和 \(1×3\) 的骨牌铺满方格，共有四种铺法。请求出铺法总数。

格式

输入格式

\(n（0≤n≤30）\)

输出格式

铺法总数。

样例1

输入样例1

3

输出样例1

4