题目描述

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

输入格式

输入一个正整数 $n$，表示有一个 $1 \times n$ 的长方形。

输出格式

输出一个数表示共有几种铺法。

样例

4

7

数据范围

• $0 < n \le 30$

来源

CodesOnline