#include<bits/stdc++.h>
 
using namespace std;
using ll = long long;
const int N = 110;
int a[N],n;
ll p,k,t;

ll qmi(ll a, ll b){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

int main(){
 
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> p >> k >> t;
    ll ans = -qmi(k, t);
    ans = (ans + p) % p;

    cout << ans << "\n";
    
    return 0;
}