#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 1000;
string A0, B0;
long long A, C, X = 37;
vector<pair<int, int> > raz0;
vector<long long> raz;
vector<long long> a;
vector<long long> f;
vector<vector<long long> > r;
long long POW(long long a, long long n, long long mod) {
  long long rez = 1ll;
  while (n > 0) {
    if (n % 2 == 1) {
      rez = (rez * a) % mod;
      n--;
    } else {
      a = (a * a) % mod;
      n /= 2;
    }
  }
  return rez;
}
void Find_Rev() {
  for (int i = 0; i < raz.size(); ++i) {
    for (int j = i + 1; j < raz.size(); ++j) {
      r[i][j] = POW(raz[i], f[j] - 1, raz[j]);
    }
  }
}
long long function(long long x, long long mod) {
  long long ans = 1ll;
  for (int i = 0; i < 11; ++i) {
    ans = (ans * x) % mod;
  }
  return (ans - 35ll * x + mod) % mod;
}
vector<long long> xx;
long long FindAns() {
  xx[0] = a[0] % raz[0];
  for (int i = 1; i < raz.size(); ++i) {
    long long x = a[i];
    for (int j = 0; j < i; ++j) {
      x = ((x - xx[j] + raz[i]) * r[j][i]) % raz[i];
    }
    xx[i] = x;
  }
  long long ans = xx.back();
  for (int i = xx.size() - 2; i >= 0; --i) {
    ans = (ans * raz[i]) % C;
    ans = (ans + xx[i]) % C;
  }
  return ans;
}
long long GetRemander(string s, long long mod) {
  long long ans = 0ll;
  long long a = 1ll;
  for (int i = s.size() - 1; i >= 0; --i) {
    ans = (ans + (a * (s[i] - '0'))) % mod;
    a *= 10;
    a %= mod;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (a < b) swap(a, b);
  while (b > 0) {
    a %= b;
    swap(a, b);
  }
  return a;
}
bool MORE(string s, long long a) {
  if (s.size() > 2) return true;
  if (s.size() == 2) return (s[1] - '0') * 10 + (s[0] - '0') - 1 >= a;
  return s[0] - '0' > a;
}
int main() {
  cin >> A0 >> B0;
  cin >> C;
  if (C == 1) {
    cout << 1 << endl;
    return 0;
  }
  A = GetRemander(A0, C);
  long long c0 = C;
  for (int i = 2; i < (int)sqrt((double)C) + 4;) {
    long long pp = 1;
    int cnt = 0;
    while (c0 % i == 0) {
      pp *= i;
      c0 /= i;
      cnt++;
    }
    if (pp > 1) {
      raz0.push_back(make_pair(i, cnt));
      raz.push_back(pp);
      f.push_back(pp - (pp / i));
    }
    i++;
  }
  if (c0 > 1) {
    raz0.push_back(make_pair(c0, 1));
    raz.push_back(c0);
    f.push_back(c0 - 1);
  }
  r.assign(raz.size(), vector<long long>(raz.size()));
  Find_Rev();
  a.resize(raz.size());
  for (int i = 0; i < raz.size(); ++i) {
    if (gcd(A, raz0[i].first) == 1ll) {
      long long B = (GetRemander(B0, f[i]) + f[i] - 1ll) % f[i];
      a[i] = POW(A, B, raz[i]);
    } else if (MORE(B0, raz0[i].second)) {
      a[i] = 0ll;
    } else {
      a[i] = 1ll;
      int B;
      if (B0.size() == 2) {
        B = (B0[1] - '0') * 10 + (B0[0] - '0') - 1;
      } else {
        B = B0[0] - '0' - 1;
      }
      for (int i = 0; i < B; ++i) {
        a[i] = (a[i] * A) % raz[i];
      }
    }
  }
  xx.resize(raz.size());
  long long ans = (FindAns() + C) % C;
  ans = ((ans * A) % C - ans + C) % C;
  if (ans == 0ll) {
    ans = C;
  }
  cout << ans << endl;
  return 0;
}
