代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,m;
char b[20000000];
int qpow(int a,int b,int mod){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
signed main(){
    scanf("%lld%lld%s",&a,&m,b);
    int tmp=m;
    int s=m;
    for(int i=2;i*i<=m;i++){
        if(m%i==0){
            s=s/i*(i-1);
            while(m%i==0) m/=i;
        }
    }
    if(m>1) s=s/m*(m-1);
    int len=strlen(b),mod=0;
    for(int i=0;i<len;i++) mod=(mod*10+b[i]-48)%s;
    printf("%lld",qpow(a,mod,tmp));
    return 0;
}