先把大数取模，然后就变成了快速幂的简单问题，

https://blog.csdn.net/csyifanZhang/article/details/105623224

↑求模运算的性质总结

// s%k
int Mod(string s, int k) {
	int res = 0, mod = 0;
	for (int i = 0; i < s.size(); i++) {
		res = mod * 10 + s[i] - '0';
		s[i] = res / k; mod = res % k;
	}
	return mod;
}

//(x^y)%z
int quickPow(int x, int y, int z) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = (res*x) % z;
		x = (x*x) % z;
		y >>= 1;
	}
	return res;	
}

int main() {
	string s; int Y, Z;
	while (cin >> s >> Y >> Z) {
		int X = Mod(s, Z);
		//x^y%k= x%k^y
		int res = quickPow(X, Y, Z);
		cout << res << endl;
	}
}