# ZeroJudge - d636: 大爆炸bomb
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d636
###### tags: `ZeroJudge` `數學` `數論`

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

int FastPowerModulo(int base, int power) {
	int answer = 1, buffer = base;
	while (power) {
		if (power & 1)
			answer = (answer * buffer) % MOD;
		buffer = (buffer * buffer) % MOD; power >>= 1;
	}
	return answer;
}

int main() {
	//cin.sync_with_stdio(false); cin.tie(nullptr);
	int base, power;
	cin >> base >> power;
	cout << FastPowerModulo(base, power) << '\n';
}