1109 - 骨牌覆盖
描述

在2*N的一个长方形方格中,用一个1*2的骨牌排满方格。

问有多少种不同的排列方法。

例如:2 * 3的方格,共有3种不同的排法。(由于方案的数量巨大,只输出 Mod 10^9 + 7 的结果)


输入

输入N(N <= 1000)


输出

输出数量 Mod 10^9 + 7


样例

输入

3

输出

3
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1