骨牌覆盖 51Nod - 1031

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

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

 

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

Input

输入N(N <= 1000)

Output

输出数量 Mod 10^9 + 7

Sample Input

3

Sample Output

3

#include <stdio.h>
#define NI 1000
typedef long long ULL;
ULL fn[NI+1];

#define N 1000000007

void setfn(int n)
{
    fn[0] = 0;
    fn[1] = 1;
    fn[2] = 2;
    for(n=3;n<=NI;n++)
        fn[n]=(fn[n-1]%N+fn[n-2]%N)%N;
}

int main(void)
{int n;
    setfn(n);
    scanf("%d",&n);

    printf("%lld\n",fn[n]);
    return 0;
}