51Nod - 

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

 

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

 

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

Input

输入N(N <= 1000)

Output

输出数量 Mod 10^9 + 7

Input示例

3

Output示例

3

 

题解： 

　　典型的斐波那契数列问题。 

 

#include 
     
       #include 
      
        using namespace std; const int MOD = 1e9 + 7; const int MAXN = 1005; int dp[MAXN]; void init(){	dp[0] = 0; 	dp[1] = 1; 	dp[2] = 2; 	for(int i=3; i