[CodeUp] #3721-블럭 채우기 7(관계기반설계)

#include <iostream>
#include <vector>
using namespace std;

vector<long long> v;
vector<long long> s;

long long b(int n);

long long a(int n){
	if(v[n-1]!=-1){
		return v[n-1]; 
	}
	else{
		if(n%2==0){
			return v[n-1] = (a(n-2) + 2*b(n-2) + 2)%100007;
		}
		else{
			return v[n-1] = 0;
		}
	}
}

long long b(int n){
	if(s[n-1]!=-1){
		return s[n-1];
	}
	else{
		return s[n-1] = (b(n-1) + a(n))%100007;
	}
}


int main(){
	int n;
	cin >> n;
	
	v.resize(n+1,-1);
	s.resize(n+1,-1);
	v[0] = 0;
	v[1] = 3;
	s[0] = 0;
	s[1] = 3;
	cout << a(n);
}