#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 y = 1; for (int i = 0; i < n; i++) { y *= x; if (y > md.first) { y -= md.first; y %= md.second; y += md.first; } } return y; /* 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; } ll md(ll x, P m) { if (x > m.first) { x -= m.first; x %= m.second; x += m.first; } return x; } ll a; P cycle(P m) { ll x = md(1, m); map mp; mp[x] = 0; for (int i = 1; i < 100000; i++) { x *= a; x = md(x, m); if (mp.count(x)) { return {mp[x], i-mp[x]}; } mp[x] = i; } assert(false); } ll solve(ll n, P m) { if (n == 0) { return md(1, m); } P mm = cycle(m); return pow_mod(a, solve(n-1, mm), m); } int main() { ll n, M; cin >> a >> n >> M; assert(1 <= a && a <= 1e9); assert(0 <= n && n <= 1e9); if (a == 1 || n == 0) { cout << 1 % M << endl; return 0; } if (M == 1) { cout << 0 << endl; return 0; } P p = cycle(P(0, M)); if (n < 10000) { cout << pow_mod(a, solve(n-1, p), P(0, M)) << endl; return 0; } assert(false); map mp; return 0; }