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

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

vector<long long> v;

long long a(int n){
	if(v[n-1]){
		return v[n-1]; 
	}
	else{
		return v[n-1] = (a(n-1) + a(n-2))%100000007;
	}
}

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