代码如下：

#include <iostream>
using namespace std;

int a,m;
int eu;
long long d;

char ch;
bool b;

int euler(int n)
{
	int ans=1;
	for(int i=2; i*i<=n; i++)
	{
		if(n%i==0)
		{
			ans*=(i-1);
			while(n%i==0) n/=i;
		}
	}
	if(n>1) ans*=(n-1);
	return ans;
}

long long qp(long long x,int y)
{
	long long ans=1;
	while(y)
	{
		if(y&1) ans=ans*x%m;
		x=x*x%m;
		y>>=1;
	}
	return ans;
}

int main()
{
	//freopen("euler.in","r",stdin);
	//freopen("euler.out","w",stdout);
	cin>>a>>m;
	a%=m;
	eu=euler(m);
	ch=getchar(); //读取空格 
	ch=getchar();
	while(isdigit(ch))
	{
		d=(d*10+ch-'0');
		if(d>=eu)
		{
			b=1;
			d%=eu;
		}
		ch=getchar();
	}
	if(b) d+=eu;
	cout<<qp(a,d);
	return 0;
}