Background

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

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

Input

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

Output

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

Samples

3

3

4

5

9

55

Limitation

对于 40% 的数据，满足n≤10。

对于 70% 的数据，满足n≤100。

对于 100% 的数据，满足n≤1000。