#include <bits/stdc++.h>
char b[1000005], n[1000005];
int expo(int a, int b, int c) {
  if (b == 0) return 1;
  int ret = expo(a, b / 2, c);
  ret = 1LL * ret * ret % c;
  if (b & 1) ret = 1LL * ret * a % c;
  return ret;
}
int mod(char* s, int c) {
  int i, ret = 0;
  for (i = 0; s[i]; i++) ret = (1LL * ret * 10 + s[i] - '0') % c;
  return ret;
}
int solve(int p, int pk, int b, char* n1) {
  int phi = pk / p * (p - 1);
  if (b % p == 0) {
    int len = 0, pwr = 0;
    while (n1[len]) len++;
    if (len > 3) return 0;
    for (len = 0; n1[len]; len++) pwr = pwr * 10 + n1[len] - '0';
    return expo(b, pwr - 1, pk);
  } else {
    int pwr = (mod(n1, phi) + phi - 1) % phi;
    return expo(b, pwr, pk);
  }
}
int main() {
  int i, j, k, c;
  scanf("%s%s%d", b, n, &c);
  int B = mod(b, c);
  int ret = (B + c - 1) % c;
  int sz = 0, N[50], M[50], PHI[50];
  int tc = c;
  for (i = 2; i * i <= tc; i++)
    if (tc % i == 0) {
      for (k = 1, j = 0; tc % i == 0; j++) {
        tc /= i;
        k *= i;
      }
      N[sz] = solve(i, k, B, n);
      M[sz] = k;
      PHI[sz++] = k / i * (i - 1);
    }
  if (tc > 1) {
    N[sz] = solve(tc, tc, B, n);
    M[sz] = tc;
    PHI[sz++] = tc - 1;
  }
  int sn = N[0], sm = M[0];
  for (i = 1; i < sz; i++) {
    int n2 = N[i], m2 = M[i];
    long long add = sm * expo(sm, PHI[i] - 1, m2) % (sm * m2);
    add = add * ((((n2 - sn) % m2) + m2) % m2) % (sm * m2);
    sn = (sn + add) % (sm * m2);
    sm *= m2;
  }
  ret = 1LL * ret * sn % c;
  if (ret == 0) ret = c;
  printf("%d\n", ret);
}
