Alice最近在玩多米诺骨牌，她突发奇想，想用她的骨牌去铺一个2×n的长方形。Alice的骨牌是1×2的长方形木片，在铺骨牌的过程中她希望能满足如下要求：
1. 骨牌必须横向或竖向放置；
2. 骨牌不能超出2×n的长方形的边界；
3. 骨牌之间不能有重叠；
4. 骨牌需要将长方形铺满(即，铺2×n的长方形需要用n块骨牌)。
请问Alice有多少种方案，用1×2的骨牌铺满2×n的长方形？

例如，n=3时，铺2×3的长方形，骨牌的铺放方案有三种，如下图：

输入一行，一个正整数n(n≥3)，表示要铺满的长方形的大小为2×n。

输出一个数，为满足上述要求的骨牌铺放方案数除以1,000,000,007的余数。

3

3

4

5

9

55