#include <bits/stdc++.h>

#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<class T>
bool chmin(T &a, T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

template<class T>
bool chmax(T &a, T b) {
    if(a >= b) return false;
    a = b;
    return true;
}

using namespace std;

ll mod_pow(ll x, ll m, int P){
    ll ret = 1;
    ll tmp = x;
    while (m > 0){
        if (m & 1){
            ret = ret * tmp % P;
        }
        m >>= 1;
        tmp = tmp * tmp % P;
    }
    return ret;
}

void naive(ll p){
    vector<ll> dp(p);
    dp[0] = 1;
    rep(i,1,p){
        vector<ll> ndp = dp;
        rep(j,0,p-1){
            ndp[j+1] += dp[j] * i;            
        }
        rep(j,0,p){
            ndp[j] %= p;
        }
        dp = ndp;
    }
    rep(i,0,p){
        cout << dp[i] << ' ';
    }
    cout << endl;
}

ll fast(ll p, ll k, ll t){
    ll v = (- k + p) % p;
    ll ans = mod_pow(v, t, p);
    if (t == p-1) ans--;
    ans += p;
    ans %= p;
    return ans;
}

int main() {
    ll p, k, t;
    cin >> p >> k >> t;
    //naive(p);
    cout << fast(p, k, t) << '\n';
}