백준 11727

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

long long arr[1001];
long long num = 0;

int main() {


	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> num;

	arr[1] = 1;
	arr[2] = 3;
	arr[3] = 5;

	for (int i = 4; i<= num; i++) {
		arr[i] = (2 * (arr[i - 1] + arr[i - 2]) - arr[i - 1]) % 10007;
	
	}

	cout << arr[num];
	
}