#include<bits/stdc++.h>
#define fi first
#define se second
//#define int ll
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int mod = 1e9 + 7, mod2 = 998244353;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const int N = 4e6 + 10, INF = 0x3f3f3f3f;
int qmi(int a, int b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a % mod;
		a = (ll)a * a % mod;
		b >>= 1;
	}
	return res;
}
vector<int>o;
ll n, k, p;
ll he = 0;
void dfs(int d, ll pr, int us) {
	if(us == p){
		he += pr;
		return;
	}
	if(d == o.size())return;
	dfs(d + 1, pr * o[d], us + 1);
	dfs(d + 1, pr, us);
}


void solve() {
	cin >> n >> k >> p;
	mod = n;
//	for (int i = 1; i < n; i++) {
//		if (i == k)continue;
//		o.push_back(i);
//	}
//	dfs(0, 1, 0);
	cout << (qmi(-k, p) + mod) % mod;
}
signed main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cout << fixed << setprecision(2);
	int T = 1;
//	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}