#include <bits/stdc++.h>
using namespace std;
struct fac {
  int p, k, pk, r;
  fac() {}
  fac(int a, int b, int c) {
    p = a;
    k = b;
    pk = c;
  }
};
int pr[100000], tag[100000 / 32 + 1], c, B, N;
vector<fac> vc;
char b[1000001], n[1000001];
int euclid(int a, int bb) {
  int pr = a, r = bb;
  int ps = 1, s = 0;
  while (r != 0) {
    int q = pr / r, h;
    h = r;
    r = pr - q * r;
    pr = h;
    h = s;
    s = ps - q * s;
    ps = h;
  }
  pr %= c;
  if (ps < 0) ps += c;
  return ps;
}
bool grk(int k) { return strlen(n) > (int)floor(log10(k)) + 1; }
int pw(int mod) {
  int ret = 1, nn = B, k = 0;
  for (int i = 0; i < strlen(n); i++) k = 10 * k + n[i] - '0';
  k--;
  while (k > 0) {
    if (k & 1) ret = (long long)ret * nn % mod;
    k >>= 1;
    nn = (long long)nn * nn % mod;
  }
  return ret;
}
int pw(int nn, int k, int mod) {
  int ret = 1;
  while (k > 0) {
    if (k & 1) ret = (long long)ret * nn % mod;
    k >>= 1;
    nn = (long long)nn * nn % mod;
  }
  return ret;
}
int cal(char x[], int mod, int k) {
  int l = strlen(x), ret = 0;
  for (int i = 0; i < l; i++) ret = (10LL * ret + x[i] - '0') % mod;
  return (ret - k + mod) % mod;
}
int main() {
  int i, k, l, h, phi, ret;
  l = sqrt(100000);
  for (i = 3; i <= l; i += 2)
    if (!(tag[i / 32] & (1 << (i % 32))))
      for (k = i * i; k < 100000; k += 2 * i) tag[k / 32] |= 1 << (k % 32);
  pr[0] = 2;
  h = 1;
  for (i = 3; i < 100000; i += 2)
    if (!(tag[i / 32] & (1 << (i % 32)))) pr[h++] = i;
  scanf("%s %s %d", b, n, &c);
  phi = h = c;
  l = sqrt(h);
  for (i = 0; pr[i] <= l; i++)
    if (h % pr[i] == 0) {
      fac f(pr[i], 0, 1);
      while (h % pr[i] == 0) {
        f.k++;
        f.pk *= pr[i];
        h /= pr[i];
      }
      phi -= phi / pr[i];
      l = sqrt(h);
      vc.push_back(f);
    }
  if (h > 1) {
    phi -= phi / h;
    vc.push_back(fac(h, 1, h));
  }
  B = cal(b, c, 0);
  N = cal(n, phi, 1);
  for (i = 0; i < vc.size(); i++)
    if (B % vc[i].p == 0) {
      if (grk(vc[i].k))
        vc[i].r = 0;
      else
        vc[i].r = pw(vc[i].pk);
    } else
      vc[i].r = pw(B, N, vc[i].pk);
  ret = 0;
  for (i = 0; i < vc.size(); i++)
    if (vc[i].r)
      ret = (ret + (long long)c / vc[i].pk * vc[i].r % c *
                       euclid(c / vc[i].pk, vc[i].pk) % c) %
            c;
  ret = (long long)ret * (B - 1) % c;
  if (ret < 0) ret += c;
  printf("%d", ret ? ret : c);
  return 0;
}
