#include <bits/stdc++.h>
using namespace std;
namespace math {
const int POW10[10] = {1,      10,      100,      1000,      10000,
                       100000, 1000000, 10000000, 100000000, 1000000000};
template <int GROUP = 9, typename BASE_SQR = int64_t>
struct BigInt {
  inline void initCharArray(const char* s, int size = -1) {
    _vs.clear();
    for (int i = (size >= 0 ? size : strlen(s)) - 1; i >= 0; i -= GROUP) {
      int v = 0;
      for (int j = min(i, GROUP - 1); j >= 0; --j) {
        v = v * 10 + s[i - j] - '0';
      }
      _vs.push_back(v);
    }
    clean();
  }
  inline void clean() {
    for (; _vs.size() > 1 && !_vs.back(); _vs.pop_back()) {
    }
  }
  template <typename T>
  inline bool operator==(T v) const {
    return !cmp<T>(v);
  }
  template <typename T>
  inline void operator-=(T v) {
    bool carry = false;
    for (size_t i = 0; i < _vs.size() || v; ++i) {
      if (i == _vs.size()) {
        _vs.push_back(0);
      }
      if (v) {
        _vs[i] -= v % POW10[GROUP];
        v /= POW10[GROUP];
      }
      if (carry) {
        --_vs[i];
      }
      carry = _vs[i] < 0;
      if (carry) {
        _vs[i] += POW10[GROUP];
      }
    }
  }
  inline BASE_SQR operator%(BASE_SQR v) {
    BASE_SQR mod = 0;
    for (int i = static_cast<int>(_vs.size()) - 1; i >= 0; --i) {
      mod = (_vs[i] + mod * POW10[GROUP]) % v;
    }
    return mod;
  }
  template <typename T>
  inline bool operator>=(T v) const {
    return cmp<T>(v) >= 0;
  }
  template <typename T>
  inline int cmp(T o, size_t idx = 0) const {
    if (!o) {
      if (idx + 1 < _vs.size()) {
        return 1;
      }
      int v = idx < _vs.size() ? _vs[idx] : 0;
      if (v != o) {
        return v < o ? -1 : 1;
      }
      return 0;
    }
    if (idx >= _vs.size()) {
      return -1;
    }
    int res = cmp(o / POW10[GROUP], idx + 1);
    if (res) {
      return res;
    }
    int mod = o % POW10[GROUP];
    if (_vs[idx] != mod) {
      return _vs[idx] < mod ? -1 : 1;
    }
    return 0;
  }
  vector<int> _vs;
};
template <typename V = int32_t>
inline V extGcd(V a, V b, V& x, V& y) {
  bool negativeA = false;
  if (a < 0) {
    negativeA = true;
    a = -a;
  }
  bool negativeB = false;
  if (b < 0) {
    negativeB = true;
    b = -b;
  }
  x = 1;
  y = 0;
  V xTmp = 0;
  V yTmp = 1;
  while (b) {
    V q = a / b;
    tie(x, xTmp) = make_tuple(xTmp, x - q * xTmp);
    tie(y, yTmp) = make_tuple(yTmp, y - q * yTmp);
    tie(a, b) = make_tuple(b, a - q * b);
  }
  if (negativeA) {
    x = -x;
  }
  if (negativeB) {
    y = -y;
  }
  return a;
}
template <typename V = int>
inline void slightFixModInline(V& v, const V& mod) {
  if (v < 0) {
    v += mod;
  }
  if (v >= mod) {
    v -= mod;
  }
}
template <typename V = int>
inline void fixModInline(V& v, const V& mod) {
  slightFixModInline<V>(v, mod);
  if (v < 0 || mod <= v) {
    v %= mod;
    slightFixModInline<V>(v, mod);
  }
}
template <typename V = int32_t>
inline V addMod(const V& a, V b, const V& mod) {
  V res = a;
  fixModInline<V>(res, mod);
  fixModInline<V>(b, mod);
  res += b;
  slightFixModInline<V>(res, mod);
  return res;
}
template <typename V = int32_t>
inline V fixMod(V v, V mod) {
  V res = v;
  fixModInline<V>(res, mod);
  return res;
}
template <typename V = int32_t, typename V_SQR = int64_t>
inline void mulModInline(V& res, V x, V mod) {
  if (!res || !x) {
    res = 0;
  } else if (res < mod / x) {
    res *= x;
  } else {
    res = static_cast<V_SQR>(res) * x % mod;
  }
}
template <typename V = int32_t, typename V_SQR = int64_t>
inline V mulMod(V a, V b, V mod) {
  mulModInline<V, V_SQR>(a, b, mod);
  return a;
}
template <typename V = int32_t, typename V_SQR = int64_t, typename V_DOUBLE = V>
inline void chineseRemainder(V a1, V n1, V a2, V n2, V& r, V& lcm) {
  a1 = fixMod<V>(a1, n1);
  a2 = fixMod<V>(a2, n2);
  V x1, x2, gcd = extGcd<V>(n1, n2, x1, x2);
  lcm = n1 / gcd * n2;
  x1 = mulMod<V, V_SQR>(fixMod<V>(x1, lcm), n1 / gcd, lcm);
  x2 = mulMod<V, V_SQR>(fixMod<V>(x2, lcm), n2 / gcd, lcm);
  lcm = n1 / gcd * n2;
  r = addMod<V_DOUBLE>(mulMod<V, V_SQR>(a1, x2, lcm),
                       mulMod<V, V_SQR>(a2, x1, lcm), lcm);
}
template <typename V = int32_t, typename EXP = int32_t,
          typename V_SQR = int64_t>
inline V expMod(V base, EXP exp, const V& mod) {
  V res = fixMod<V>(1, mod);
  for (; exp > 0; exp >>= 1) {
    if (exp & 1) {
      mulModInline<V, V_SQR>(res, base, mod);
    }
    mulModInline<V, V_SQR>(base, base, mod);
  }
  return res;
}
template <typename V = int>
inline V subMod(V a, V b, V mod) {
  V res = a;
  fixModInline<V>(res, mod);
  fixModInline<V>(b, mod);
  if (res >= b) {
    res -= b;
  } else {
    res = mod - (b - res);
  }
  slightFixModInline<V>(res, mod);
  return res;
}
namespace {
const int PRIME_WHEEL[4] = {2, 3, 5, 7};
const int PRIME_LCM = 2 * 3 * 5 * 7;
const int COPRIME_CNT = 48;
const int COPRIMES[COPRIME_CNT] = {
    1,   11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,
    53,  59,  61,  67,  71,  73,  79,  83,  89,  97,  101, 103,
    107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157,
    163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209};
}  // namespace
class PrimeIterator {
 public:
  inline PrimeIterator(int n = 30) {
    precompute_();
    init(n);
  }
  inline void init(int n) {
    int size = n / PRIME_LCM + 1;
    sieve_.assign(size, 0);
    sieve_[0] = 1;
    int bound = static_cast<int>(sqrt(n) + 1);
    memcpy(mul_, mulInit_, sizeof(mul_));
    auto* sieve = sieve_.data();
    const auto* sieveEnd = sieve + size;
    for (int base = 0; base <= bound; base += PRIME_LCM, ++sieve) {
      for (int i = 0; i < COPRIME_CNT; ++i) {
        if (!((*sieve >> i) & 1)) {
          int v = base + COPRIMES[i], vv = v * v;
          tag_(coprimesInv_[vv % PRIME_LCM], sieve_.data() + vv / PRIME_LCM,
               sieveEnd, mul_[i], nextIdx_[i]);
        }
        for (int k = 0; k < COPRIME_CNT; ++k) {
          mul_[i][k] += mulStep_[i][k];
        }
      }
    }
  }
  inline void iterate(int n, const std::function<bool(int)>& processor) const {
    for (int p : PRIME_WHEEL) {
      if (p < n) {
        if (!processor(p)) {
          return;
        }
      }
    }
    int base = 0;
    for (const auto& sieve : sieve_) {
      for (int idx = 0; idx < COPRIME_CNT; ++idx) {
        if ((sieve >> idx) & 1) {
          continue;
        }
        int v = base + COPRIMES[idx];
        if (v >= n) {
          break;
        }
        if (!processor(v)) {
          return;
        }
      }
      base += PRIME_LCM;
      if (base >= n) {
        break;
      }
    }
  }

 private:
  inline void precompute_() {
    memset(coprimesInv_, 0xFF, sizeof(coprimesInv_));
    for (int i = 0; i < COPRIME_CNT; ++i) {
      coprimesInv_[COPRIMES[i]] = i;
    }
    for (int i = 0; i < COPRIME_CNT; ++i) {
      for (int j = 0; j < COPRIME_CNT; ++j) {
        int sum = COPRIMES[i] + COPRIMES[j], step = 1, delta = 0;
        if (sum >= PRIME_LCM) {
          sum -= PRIME_LCM;
          ++delta;
        }
        for (; coprimesInv_[sum] < 0; ++step) {
          sum += COPRIMES[i];
          if (sum >= PRIME_LCM) {
            sum -= PRIME_LCM;
            ++delta;
          }
        }
        nextIdx_[i][j] = coprimesInv_[sum];
        mulInit_[i][j] = delta;
        mulStep_[i][j] = step;
      }
    }
  }
  inline void tag_(int idx, long long* sieve, const long long* sieveEnd,
                   const int* mul, const int* nextIdx) {
    while (sieve < sieveEnd) {
      *sieve |= 1LL << idx;
      sieve += mul[idx];
      idx = nextIdx[idx];
    }
  }
  int mul_[COPRIME_CNT][COPRIME_CNT];
  int coprimesInv_[PRIME_LCM];
  int mulInit_[COPRIME_CNT][COPRIME_CNT];
  int mulStep_[COPRIME_CNT][COPRIME_CNT];
  int nextIdx_[COPRIME_CNT][COPRIME_CNT];
  vector<long long> sieve_;
};
class PrimeGenerator {
 public:
  inline PrimeGenerator(int n, int capacity = -1) { init(n, capacity); }
  inline void init(int n, int capacity = -1) {
    pi.init(n);
    primes.clear();
    if (capacity >= 0) {
      primes.reserve(capacity);
    }
    pi.iterate(n, [this](uint32_t prime) {
      primes.push_back(prime);
      return true;
    });
  }
  vector<int> primes;

 private:
  PrimeIterator pi;
};
}  // namespace math
const int MAXL = 1000000 + 2;
char s[MAXL];
math::BigInt<> biBase, e;
int base;
math::PrimeGenerator pg(40000);
inline int calcSub(int mod, int modBase, int modExp) {
  if (base % modBase) {
    return math::expMod<int, int, int64_t>(base % mod,
                                           e % (mod - mod / modBase), mod);
  }
  int normBase = base, baseExp = 0;
  do {
    normBase /= modBase;
    ++baseExp;
    if (e >= (modExp + modBase - 1) / modBase) {
      return 0;
    }
  } while (!(normBase % modBase));
  assert(e._vs.size() == 1);
  return math::expMod<int, int, int64_t>(math::fixMod(base, mod), e._vs[0],
                                         mod);
}
inline int calcExp(int mod) {
  if (e == 0) {
    return math::fixMod(1, mod);
  }
  if (mod == 1 || base == 0) {
    return 0;
  }
  int res = 0, resMod = 1;
  for (size_t i = 0; i < pg.primes.size() && pg.primes[i] <= mod / pg.primes[i];
       ++i) {
    if (mod % pg.primes[i]) {
      continue;
    }
    int newMod = mod / pg.primes[i];
    int modExp = 1;
    for (; !(newMod % pg.primes[i]); ++modExp) {
      newMod /= pg.primes[i];
    }
    math::chineseRemainder(res, resMod,
                           calcSub(mod / newMod, pg.primes[i], modExp),
                           mod / newMod, res, resMod);
    mod = newMod;
  }
  if (mod > 1) {
    math::chineseRemainder(res, resMod, calcSub(mod, mod, 1), mod, res, resMod);
  }
  return res;
}
int main() {
  while (scanf("%s", s) != EOF) {
    int mod;
    biBase.initCharArray(s);
    scanf("%s%d", s, &mod);
    base = biBase % mod;
    e.initCharArray(s);
    e -= 1;
    int res = math::mulMod(
        calcExp(mod), math::subMod<int>(base, math::fixMod(1, mod), mod), mod);
    printf("%d\n", res ? res : mod);
  }
}
