[BOJ-11726]2xN타일링

    // 2*n 

    // dy(1) : 1 

    // dy(2) : 2

    // dy(3) : 1 * dy(2)

    //       : 1 * dy(1) -> 위 경우에서 다 체크.

    // dy(n) = dy(n-1) + dy(n-2) 

    // n>2

#include<cstdio>
#include<vector>
using namespace std;
const int DIV = 10007;
typedef vector<int> VI;
VI v;
int dy(int n){
    int& ret = v[n];
    if(ret!=-1)return ret;
    return ret = (dy(n-1)+dy(n-2))%DIV;
}
int main(){
    int n; scanf("%d", &n);    
    v = VI(n+1,-1);
    v[0] = 0;
    v[1] = 1;
    v[2] = 2;
    printf("%d",dy(n));   
    return 0;
}