#include <bits/stdc++.h>
using std::bitset;
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::map;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::string;
using std::vector;
class MyTimer {
 public:
  void reset() {}
  void report() {}
} myTimer;
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
  return a > b ? a = b, true : false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
  return a < b ? a = b, true : false;
}
inline int readint() {
  int a = 0;
  char c = getchar(), p = 0;
  while (isspace(c)) c = getchar();
  if (c == '-') p = 1, c = getchar();
  while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
  return p ? -a : a;
}
inline long long readLL() {
  long long a = 0;
  char c = getchar(), p = 0;
  while (isspace(c)) c = getchar();
  if (c == '-') p = 1, c = getchar();
  while (isdigit(c)) a = a * 10 + c - '0', c = getchar();
  return p ? -a : a;
}
const int maxN = 1000000 + 233;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
char _b[maxN], _n[maxN], *B = _b, *N = _n;
int lb, ln;
void dec(char *s, int &len) {
  int i = len - 1;
  for (; s[i] == 0; s[i--] = 9)
    ;
  s[i]--;
}
long long b, n;
long long m;
long long qpow(long long a, long long b, long long m) {
  long long r = 1;
  while (b) {
    if (b & 1) (r *= a) %= m;
    b >>= 1;
    (a *= a) %= m;
  }
  return r;
}
void merge(long long &a, long long &n, long long b, long long m) {
  if (n < m) std::swap(a, b), std::swap(n, m);
  while (a % m != b) a += n;
  n *= m;
}
long long getmod(long long x) {
  long long r = 0;
  for (int i = 0; i < ln; ++i) r = (r * 10 + N[i]) % x;
  return r;
}
long long factor(long long tot) {
  long long r = 0, m = 1;
  auto calc = [&](long long x) -> void {
    long long n = 1;
    while (tot % x == 0) tot /= x, n *= x;
    long long phi = n / x * (x - 1);
    if (b % x != 0)
      merge(r, m, qpow(b, getmod(phi), n), n);
    else
      merge(r, m, 0, n);
  };
  for (long long i = 2; i * i <= tot; ++i)
    if (tot % i == 0) calc(i);
  if (tot > 1) calc(tot);
  return r;
}
long long solve() {
  if (ln >= 15)
    return factor(m);
  else {
    for (int i = 0; i < ln; ++i) {
      if (i == 0) n = 0;
      n = (n * 10 + N[i]);
    }
    return qpow(b, n, m);
  }
}
int main() {
  scanf("%s %s %lld", B, N, &m);
  lb = strlen(B), ln = strlen(N);
  for (int i = 0; i < lb; ++i) B[i] -= '0';
  for (int i = 0; i < ln; ++i) N[i] -= '0';
  dec(N, ln);
  b = 0;
  for (int i = 0; i < lb; ++i) b = (b * 10 + B[i]) % m;
  long long ans = solve();
  if (b-- == 0) b = m - 1;
  ans = ans * b % m;
  printf("%lld\n", ans ? ans : m);
  return 0;
}
