# ZeroJudge - f372: 崑棋的臭豆腐
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=f372
###### tags: `ZeroJudge` `數學`

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

int powers[32] = { 1, 3 };

void Initialize() {
	for (int i = 2; i < 32; ++i)
		powers[i] = (powers[i - 1] * powers[i - 1]) % MOD;
}

int FastPower(int power) {
	int answer = 1, term = 1;
	while (power) {
		if (power & 1)
			answer = (answer * powers[term]) % MOD;
		power >>= 1; ++term;
	}
	return answer;
}

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