#include using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef pair P; // x^n % md ll pow_mod(ll x, ll n, P md) { ll r = 1; while (n) { if (n & 1) { r = r * x; if (r > md.first) { r -= md.first; r %= md.second; r += md.first; } } x = x * x; if (x > md.first) { x -= md.first; x %= md.second; x += md.first; } n >>= 1; } return r; } // x^n % md ll pow_mod(ll x, ll n, ll md) { ll r = 1; while (n) { if (n & 1) r = (r * x) % md; x = (x * x) % md; n >>= 1; } return r % md; } P cycle(ll a, ll m) { ll x = 1 % m; map mp; mp[x] = 0; for (int i = 1; i < 100000; i++) { x *= a; x %= m; if (mp.count(x)) { return {mp[x], i}; } mp[x] = i; } assert(false); } int main() { ll a, n, m; cin >> a >> n >> m; if (n == 0) { cout << 1 % m << endl; return 0; } if (m == 1) { cout << 0 << endl; return 0; } n--; P p = cycle(a, m); ll x = 1; if (x > p.first) { x -= p.first; x %= p.second; x += p.first; } map mp; mp[x] = 0; for (int i = 1; i < 100000; i++) { x = pow_mod(a, x, p); if (mp.count(x)) { if (n-1 < mp[x]) break; n -= mp[x]; n %= i - mp[x]; n += mp[x]; break; } mp[x] = i; } x = 1; for (int i = 0; i < n; i++) { x = pow_mod(a, x, p); } cout << pow_mod(a, x, m) << endl; return 0; }