#include <bits/stdc++.h>
#define int long long
using namespace std;

int MOD;

long long power(long long a, int b) {
  assert(b >= 0);
  int base = (a % MOD + MOD) % MOD, ans = 1ll;
  while (b) {
    if (b & 1) {
      ans = ans * base % MOD;
    }
    base = base * base % MOD + MOD;
    b >>= 1;
  }
  return (ans + MOD) % MOD;
}

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

  int k, t;

  while (cin >> MOD >> k >> t) {
    int ans = power(-k, t);
    cout << ans << endl;
  }

  return 0;
}