#include <iostream>
using namespace std;

int main() {
	int a, n, z, result, x;
	cout << "Enter a: ";
	cin >> a;
	cout << "Enter n: ";
	cin >> n;
	cout << "Enter z: ";
	cin >> z;

	result = 1;
	x = a % z;
	while (n > 0) {
		if ( n % 2 == 1)
			result = (result * x) % z;
		x = (x * x) % z;
		n = n/2;
	}
	cout << result << '\n';
	return 0;
}