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

const ll N = 1e6 + 1;
const ll M = 1e9 + 7;

ll powerMod(ll a, ll b, ll m) {
    ll res = 1;
    for (; b; a = a * a % m, b >>= 1)
        if (b & 1) res = res * a % m;
    return res;
}

ll p, k, t;

void doTest(ll testID) {
    cin >> p >> k >> t;
    cout << (0ll - powerMod(k, t, p) + p) % p;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int test = 1; 
    // cin >> test;
    for (int _ = 1; _ <= test; _ ++) doTest(test);
}