骨牌铺法(domino)

题目背景

多米诺骨牌是一种木制、骨制或塑料制成的长方体骨牌，通过按一定间距排列成行，轻轻碰倒第一枚骨牌，其余的骨牌就会产生连锁反应依次倒下。

题目描述

有 一个长度为n 的一个长方形区域，用长度分别为 1、2 和 3 的骨牌铺满这个区域。 例如当 n=3 时， 此时用 1、2 和 3 的骨牌铺满方格，共有四种铺法。如下图：

（1,1,1）（1,2）（2,1）（3）

输入格式

输出格式

样例 #1

样例输入 #1

3

样例输出 #1

4