#include <bits/stdc++.h>
#define endl '\n'
#define pll pair<ll, ll>
#define tll tuple<ll, ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define x first
#define y second
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, j ,k) for(int i = (j); i >= (k); i--)
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
#define int ll
const ll maxn = 2e5 + 10;
const ll mod = 998244353;
const ll inf = 0x3f3f3f3f;
int p;
int qpow(long long a, int b) {
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}

void solve() {
  int k, t;
  cin >> p >> k >> t;
  if (t & 1)
    cout << (p - qpow(k, t) + p) % p << endl;
  else 
    cout << qpow(k, t) % p << endl;
}

signed main() {
  ios;
  //freopen("sample.txt", "r", stdin);
  //freopen("resout.txt", "w", stdout);
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}