#include <bits/stdc++.h>
#define FAST                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define debug(x) cout << endl << #x << ": " << x << endl
#define endl "\n"
#define PII pair<int, int>
#define PID pair<int, double>
#define PDI pair<double, int>
#define ls p << 1
#define rs (p << 1) + 1
#define pb push_back
#define ppb pop_back
#define fs first
#define sc second
#define int ll
#define Random(x)                       \
    mt19937_64 rnd(random_device {}()); \
    uniform_int_distribution<int> u(1, (x)-5);
using ll = long long;
using ull = unsigned long long;
using db = double;
using namespace std;
const int N = 1e5, INF = 1e9;

int p, k, t;

int qmi(int x, int q) {
	int res = 1;
	while(q) {
		if(q & 1) res = res * x % p;
		x = x * x % p;
		q >>= 1;
	}
	return res;
}

void solve() {
    cin >> p >> k >> t;
    cout << (p - qmi(k, t)) % p;
}

signed main() {
    FAST;
    int T = 1;
    // cin >> T;
    while(T--) solve();
}