[C++] 2*n 타일링 2 - 11727

#include <iostream>
using namespace std;

int a[1001] = {0};

int tiling(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 3;
	if (a[n] != 0) return a[n];
	return a[n] = (tiling(n - 1) + (tiling(n - 2)*2)) % 10007;
		
}

int main()
{
	int N = 0;
	cin >> N;
	cout << tiling(N);
	
	
	return 0;
}