#include <bits/stdc++.h>
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
using ll = long long;
using ld = long double;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
using namespace std;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
map<ll, ll> w;
ll n, x, m;
ll fc(ll st, ll p) {
  ll pos = 0;
  ll t = st;
  ll ans = 0;
  while (pos <= p) {
    ans += t;
    t = t * t;
    t %= m;
    pos++;
  }
  return ans;
}
int main() {
  ll ans = 0;
  cin >> n >> x >> m;
  ll pos = 0;
  ll t = x, st = 0, e = 0, now;
  w[0] = 1;
  while (w[t] == 0 && pos <= n) {
    w[t] = pos;
    ans += t;
    t = t * t;
    t %= m;
    pos++;
    now = t;
    e = w[t];
    st = pos - w[t];
  }
  if (t == 1)
    ans += n - pos;
  else if (t != 0 && pos < n) {
    ll num = n - e;
    ll b = fc(x, e - 1);
    ans = b + (ans - b) * (num / st) + fc(now, num % st - 1);
  }
  cout << ans << endl;
}
