#include<bits/stdc++.h>

using namespace std;

#define int long long
int p, k, t;
int ans;

int qpow(int a, int b) {
	int cnt = 1;
	while(b) {
		if(b & 1) cnt = cnt * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return cnt;
}

void solve(){
	cin >> p >> k >> t;
	int h = -qpow(k, t);
	ans = (h + p) % p;
	cout << ans << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t_ = 1;
//	cin >> t_;
	while(t_ --){
		solve();
	}
}