#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main() {
  ll n, x, m;
  cin >> n >> x >> m;
  vector<ll> a(n);
  a[0] = x;
  int start = m, stop = m;
  for (int i = 1; i < m; i++) {
    a[i] = (a[i - 1] * a[i - 1]) % m;
    for (int j = 0; j < i; j++) {
      if (a[i] == a[j]) {
        start = j;
        stop = i - 1;
        break;
      }
    }
    if (stop != m) break;
  }
  ll ans = 0;
  for (ll i = 0; i < (ll)(start); i++) ans += a[i];
  int len = stop - start + 1;
  int reply = (n - start) / len;
  int left = (n - start) % len;
  ll arealeft = 0;
  for (int i = start; i < start + left; i++) {
    arealeft += a[i];
  }
  ll area = arealeft;
  for (int i = start + left; i <= stop; i++) {
    area += a[i];
  }
  ans += area * reply + arealeft;
  cout << ans << endl;
}
