题目描述

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