#include <iostream>

using namespace std;

size_t modexp(size_t x, size_t y, size_t N) {
	if (y == 0) return 1;
	size_t z = modexp(x, y / 2, N);
	if (y % 2 == 0) {
		return (z*z) % N;
	} else {
		return (x*z*z) % N;
	}
}

int main() {
	size_t x, y, N;
	cout << "x= "; cin >> x;
	cout << "y= "; cin >> y;
	cout << "N= "; cin >> N;
	cout << modexp(x, y, N);
	cin.get(); cin.get();
	return 0;
}