# ZeroJudge - a272: 猥瑣罐頭下樓梯
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=a272
###### tags: `ZeroJudge` `快速冪` `矩陣`

#include <iostream>
using namespace std;
#define MOD 10007

int matrix[32][2][2] = { {}, { { 0, 1 }, { 1, 1 } } };

void Initialize() {
	for (int i = 2; i < 32; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k) {
				for (int l = 0; l < 2; ++l)
					matrix[i][j][k] += matrix[i - 1][j][l] * matrix[i - 1][l][k];
				matrix[i][j][k] %= MOD;
			}
}

int FindNthFinbonacci(int number) {
	int answer[2][2] = { { 1, 0 }, { 0, 1 } }, buffer[2][2], power = 1;
	while (number) {
		if (number & 1) {
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					buffer[i][j] = 0;
					for (int k = 0; k < 2; k++)
						buffer[i][j] += answer[i][k] * matrix[power][k][j];
					buffer[i][j] %= MOD;
				}
			}
			for (int i = 0; i < 2; i++)
				for (int j = 0; j < 2; j++)
					answer[i][j] = buffer[i][j];
		}
		number >>= 1; ++power;
	}
	return (answer[0][0] + answer[0][1]) % MOD;
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	Initialize();
	int number;
	while (cin >> number)
		cout << FindNthFinbonacci(number) << '\n';
}