1109 - 骨牌覆盖
Description

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

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

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


Input

输入N(N <= 1000)


Output

输出数量 Mod 10^9 + 7


Examples

Input

3

Output

3
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1