백준 11727 타일링

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

vector<int> arr(1001, -1);

int Dp(int n)
{
	if (arr[n] != -1)
	{
		return arr[n];
	}

	arr[n] = (Dp(n - 1) + Dp(n-2)*2) % 10007;

	return arr[n];
}


int main(void)
{
	arr[1] = 1;
	arr[2] = 3;

	int n;
	cin >> n;

	int a = Dp(n);

	cout << a;


	return 0;
}