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

ll M, k, n;
ll trace(ll x){
    if(x == 0){
        return 2;
    }else if(x == 1){
        return k;
    }else if(x == 2){
        return k*k - 2;
    }
    ll mid = x/2;
    ll rest = x - mid;
    return (trace(mid)*trace(rest) - trace(abs(mid - rest)))%M;
}
int main(){
    cin>>M>>k>>n;
    ll ans = trace(n);
    cout<<ans<<endl;
return 0;
}