RT, thx

#include <bits/stdc++.h>
#define int long long
using namespace std;

int ksm(int a, int b, int p)
{
	int ans = 1, res = a;
	while(b)
	{
		if(b % 2)ans *= res;
		res *= res;
		ans %= p, res %= p;
		b /= 2;
	}
	return ans;
}

int phi1(int p)
{
	int ans = p;
	for(int i = 2;i * i <= p;i++)
	{
		if(p % i == 0)
		{
			ans = ans*  (p - 1) / p;
			while(p % i == 0)p /= i;
		}
	}
	if(p != 1)
	{
		 ans = ans * (p - 1) / p;
	}
	return ans;
}

signed main()
{
	int a, b, p;
	cin >> a >> p;
	int p1 = phi1(p);
	int mod = p1;
	register int x = 0, f = 0;
	register char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c <= '9' && c >= '0')
	{
		x = x * 10 + c - '0';
		if(x > mod)f = 1, x %= mod;
		c = getchar();
	}
	b = x;
	if(f)b += p1;
	cout << ksm(a, b, p);
	return 0;
}