#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (y >= 0);
    x %= p; if (x < 0) x += p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
int solve(int a, int n, int m) {
    vector<int> tower(m+1);
    tower[0] = 1;
    repeat (i,m) tower[i+1] = powmod(a, tower[i], m);
    int x = whole(find, tower, tower.back()) - tower.begin();
    int y = tower.size() - x;
    assert (y != 0);
    return tower[(n - x) % y + x];
}
int main() {
    int a, n, m; cin >> a >> n >> m;
    cout << solve(a % m, n, m) << endl;
    return 0;
}