样例 #2 没过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m;
ll read() {
    string str;
    cin>>str;
    ll res=0;
    for(int i=0;i<str.length();i++) res=(res*10%m+str[i]-'0')%m;
    return res;
}
ll phi(ll n) {
    ll res=n;
    for(ll i=2;i*i<=n;i++) {
        if(n%i==0) {
            res=res/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) res=res/n*(n-1);
    return res;
}
ll binpow(ll a,ll b) {
    if(b==0) return 1;
    if(b==1) return a;
    ll res=binpow(a,b/2);
    if(b&1) return res*res%m*a%m;
    else return res*res%m;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll a;
    cin>>a>>m;
    a%=m;
    ll b=read();
    ll p=phi(m);
    if(b<p) cout<<binpow(a,b)<<'\n'; 
    else cout<<binpow(a,b%p+p)<<'\n';
    return 0;
}