Description

小明家门口有一条很长的长廊，但由于年代久远现在地面已经破旧不堪。于是小明决定对其进行翻修，主要工作是使用一批1×1 和 2×2 的古式地砖重新铺满长廊地面。长廊可以看作 n×3 大小的矩形，现请问小明可以有多少种不用的方案？结果可能很大，请对10^9+7取余输出。

例如：n=1 时：1×3 的长廊方法就一个，直接由三个 1×1 的地砖铺满。

n=2 时：2×3 的长廊可以由下面 3 种方案铺满：

   方法一：                                                                方法二：                                                                 方法三：

Input Format

第一行：一个整数 n，表示长廊的长度。

Output Format

输出铺满 n×3 的长廊的方案数。

3

5

Hint

【数据范围】
对于 50%的数据，1≦n≦30;
对于 100%的数据，1≦n≦100;