(C++) 백준 11727번 2×n 타일링 2

#include <iostream> 
#define mod 10007
using namespace std;

int D[1000];



int Solution(int n){
	
	if(D[n]>0) return D[n];
	if(n==1) return 1;
	if(n==2) return 3;
	
	D[n]=(Solution(n-1)%10007 +Solution(n-2)*2%10007)%10007;
	
	return D[n];
}


int main(){
	
	int n;
	cin>>n;

	cout<<Solution(n);
}