【题目描述】

有 $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$ 的骨牌铺满方格，共有四种铺法。如下图：

【输入样例】

3

【输出样例】

4