#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long inf = 1e18;
int main() {
  long long n, x, m;
  cin >> n >> x >> m;
  vector<long long> p(m + 1);
  vector<bool> c(m + 1, false);
  for (int i = 1; i <= m; i++) {
    p[i] = x % m;
    x *= x;
  }
  long long sum = 0;
  long long num = x;
  long long nn;
  while (1) {
    if (c[num]) {
      nn = num;
      c[num] = false;
      break;
    }
    c[num] = true;
    num *= num;
    num %= m;
  }
  int count = 1;
  while (true) {
    num *= num;
    num %= m;
    if (!c[num])
      break;
    else
      count++;
  }
  num = x;
  long long ccc = 0;
  while (true) {
    if (num == nn) break;
    sum += p[ccc];
    ccc++;
  }
  n -= ccc;
  long long q = n / count, r = n % count;
  for (int i = 0; i < count; i++) {
    if (i <= r)
      sum += (q + 1) * p[i];
    else
      sum += q * p[ccc + 1 + i];
  }
  cout << sum << endl;
  return 0;
}
