RT，求查错qwq

#include<bits/stdc++.h>
using namespace std;
long long phi(long long x){
    long long ans=x;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            ans=ans/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}
long long a,p,b;
long long ksm(long long a,long long b){
    long long ans=1,base=a;
    while(b>0){
        ans%=p;
        base%=p;
        if(b&1) ans*=base;
        base*=base;
        b>>=1;
    }
    return ans%p;
}
string bb;
int main(){
    cin>>a>>p>>bb;
    long long phi_of_p=phi(p);
    for(int i=0;i<bb.size();i++){
        b*=10;
        b+=int(bb[i]-'0');
        b%=phi_of_p;
    }
    b+=phi_of_p;
    cout<<ksm(a,b);
}