#include <cstdio>
#define int long long
using namespace std;

int qpow(int a,int b,int mod) {
	int res = 1;
	while(b) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
signed main () {
	int a,m,b = 0; scanf("%lld%lld",&a,&m);
	int res = 1;
	for(int i = 2;i <= m;i ++) {
		if(m % i != 0) {
			res ++;
		}
	}
	int flag = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9') {
		if(b * 10 + c - '0' >= res) {
			flag = 1;
		}
		b = (b * 10 + c - '0') % res;
		c = getchar();
	}
	if(! flag) printf("%lld\n",qpow(a,b,m));
	else {
		b += res;
		printf("%lld\n",qpow(a,b % res + res,m));
	}
	return 0;
}