题目描述

在 $1×n$ 的一个长方形方格中，用 $1×1$、$1×2$、$1×3$ 的骨牌铺满方格，输入 $n$，输出铺放方案的总数。例如 $n=3$ 时，为 $1× 3$ 方格，骨牌的铺放方案有四种。

输入格式

输入数据由多行组成，每行包含一个整数 $n$，表示该测试实例的长方形方格的规格是 $1×n$。