// Slower C++ solution:
#include<bits/stdc++.h>

//#include<atcoder/all>

using namespace std;

//using namespace atcoder;

#define rep(i,n) for(ll i=0;i<n;i++)

#define repl(i,l,r) for(ll i=(l);i<(r);i++)

#define per(i,n) for(ll i=n-1;i>=0;i--)

#define perl(i,r,l) for(ll i=r-1;i>=l;i--)

#define fi fist

#define se second

#define pb push_back

#define ins insert

#define all(x) (x).begin(),(x).end()

using ll=long long;

using vl=vector<ll>;

using vvl=vector<vector<ll>>;

const ll MOD9=1000000007;

const ll MOD=998244353;

const int inf=1e9+10;

const ll INF=4e18;

const ll dy[8]={1,0,-1,0,1,1,-1,-1};

const ll dx[8]={0,-1,0,1,1,-1,1,-1};

using Graph = vector<vector<int>>;



// dijkstra　

struct edge{ll to, cost;};

typedef pair<ll,ll> P;

struct graph{

  ll V;

  vector<vector<edge> > G;

  vector<ll> d;



  graph(ll n){

    init(n);

  }



  void init(ll n){

    V = n;

    G.resize(V);

    d.resize(V);

    rep(i,V){

      d[i] = INF;

    }

  }



  void add_edge(ll s, ll t, ll cost){

    edge e;

    e.to = t, e.cost = cost;

    G[s].push_back(e);

  }



  void dijkstra(ll s){

    rep(i,V){

      d[i] = INF;

    }

    d[s] = 0;

    priority_queue<P,vector<P>, greater<P> > que;

    que.push(P(0,s));

    while(!que.empty()){

      P p = que.top(); que.pop();

      ll v = p.second;

      if(d[v]<p.first) continue;

      for(auto e : G[v]){

        if(d[e.to]>d[v]+e.cost){

          d[e.to] = d[v]+e.cost;

          que.push(P(d[e.to],e.to));

        }

      }

    }

  }

};

// dijkstra end





class UnionFind

{

public:

  ll par[100005];

  ll depth[100005];

  ll nGroup[100005];

 

  UnionFind(ll n) {

    init(n);

  }

 

  void init(ll n) {

    for(ll i=0; i<n; i++) {

      par[i] = i;

      depth[i] = 0;

      nGroup[i] = 1;

    }

  }

 

  ll root(ll x) {

    if(par[x] == x) {

      return x;

    } else {

      return par[x] = root(par[x]);

    }

  }

 

  bool same(ll x, ll y) {

    return root(x) == root(y);

  }

 

  void unite(ll x, ll y) {

    x = root(x);

    y = root(y);

    if(x == y) return;

 

    if(depth[x] < depth[y]) {

      par[x] = y;

      nGroup[y] += nGroup[x];

      nGroup[x] = 0;

    } else {

      par[y] = x;

      nGroup[x] += nGroup[y];

      nGroup[y] = 0;

      if(depth[x] == depth[y])

        depth[x]++;

    }

  }

};

// unionfind end



// nCr

const ll MAX = 500010;

ll fac[MAX], finv[MAX], inv[MAX];



void COMinit() {

    fac[0] = fac[1] = 1;

    finv[0] = finv[1] = 1;

    inv[1] = 1;

    for (ll i = 2; i < MAX; i++){

        fac[i] = fac[i - 1] * i % MOD;

        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;

        finv[i] = finv[i - 1] * inv[i] % MOD;

    }

}



// nCr end



// tree DP

vector<ll> depth;

vector<ll> f;

vector<ll> g;

void dfs(const Graph &G, ll v, ll p, ll d) {

    depth[v] = d;

    for (auto nv : G[v]) {

        if (nv == p) continue; 

        dfs(G, nv, v, d+1);

    }





    f[v] = 1;

    g[v] = 1; 

    for (auto c : G[v]) {

        if (c == p) continue;

        f[v]*=g[c];

        f[v]%=MOD;

        g[v]*=f[c];

        g[v]%=MOD;

        }

    f[v]+=g[v];

    f[v]%=MOD;

}

// tree DP end





template<ll MOD> struct Fp {

    ll val;

    constexpr Fp(ll v = 0) noexcept : val(v % MOD) {

        if (val < 0) val += MOD;

    }

    constexpr ll getmod() { return MOD; }

    constexpr Fp operator - () const noexcept {

        return val ? MOD - val : 0;

    }

    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }

    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }

    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }

    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }

    constexpr Fp& operator += (const Fp& r) noexcept {

        val += r.val;

        if (val >= MOD) val -= MOD;

        return *this;

    }

    constexpr Fp& operator -= (const Fp& r) noexcept {

        val -= r.val;

        if (val < 0) val += MOD;

        return *this;

    }

    constexpr Fp& operator *= (const Fp& r) noexcept {

        val = val * r.val % MOD;

        return *this;

    }

    constexpr Fp& operator /= (const Fp& r) noexcept {

        ll a = r.val, b = MOD, u = 1, v = 0;

        while (b) {

            ll t = a / b;

            a -= t * b; swap(a, b);

            u -= t * v; swap(u, v);

        }

        val = val * u % MOD;

        if (val < 0) val += MOD;

        return *this;

    }

    constexpr bool operator == (const Fp& r) const noexcept {

        return this->val == r.val;

    }

    constexpr bool operator != (const Fp& r) const noexcept {

        return this->val != r.val;

    }

    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {

        return os << x.val;

    }

    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, ll n) noexcept {

        if (n == 0) return 1;

        auto t = modpow(a, n / 2);

        t = t * t;

        if (n & 1) t = t * a;

        return t;

    }

};

using mint = Fp<MOD>;



mint calc(ll N, ll K) {

    mint res = 1;

    for (ll n = 0; n < K; ++n) {

        res *= (N - n);

        res /= (n + 1);

    }

    return res;

}

mint COM(ll n, ll k){

    if (k == 0) return 1;

    if (n < k) return 0;

    if (n < 0 || k < 0) return 0;

    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;

} 





int main() {

  ll n,x,m; cin>>n>>x>>m;

  ll a[100005]={};

  ll loop = 1;

  ll ca = x;

  ll k = x;

  ll sum[100005] = {};

  a[x]++;

  ll c[100005]={};

  sum[1]=x;

  c[x]=1;

  while(1){

    k = (k*k)%m;

    ca += k;

    loop++;

    a[k]++;

    if(loop==n)break;

    if(a[k]==2)break;

    c[k]=loop;

    sum[loop] += k+sum[loop-1];

  }

  if(loop==n){

    cout << ca << endl;

    return 0;}

  ca-=k;

  //cout << ca << endl;

  ll sum1 = sum[loop-1]-sum[c[k]-1];

  ll roop = loop - c[k];

  ll len = n - loop + 1;

  ll mo = len%roop;

  ca += sum1*(len/roop);

  for(ll i=0; i<mo; i++){

    ca += k;

    k = (k*k)%m;

  }

  //for(int i=0; i<=6; i++)cout << sum[i] << endl;

  cout << ca << endl;

}




// Faster C++ solution for the same problem (measured speedup: 1.7933362359991438x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)

#define per(i,n) for(int i = n-1; i >= 0; i--)

typedef long long ll;

typedef pair<int, int> P;

typedef pair<long long, long long> Pll;

typedef vector<int> vi;

typedef vector<ll> vll;

const long long mod = 1000000007LL;



int main() {

  ll check[110000]={};

  ll n, x, m;

  cin >> n >> x >> m;

  if(x==0) {

    cout << 0 << endl;

    return 0;

  }

  vll v;

  ll cnt = 0LL;

  ll a = x;

  rep(i,m*2) {

    v.push_back(a);

    cnt += a;

    check[a] = true;

    a *= a;

    a %= m;

    if(check[a]) break;

    if(a==0) {

      cout << cnt << endl;

      return 0;

    }

  }

  if(a==x) {

    ll s = v.size();

    ll ans = 0LL;

    ll c = n - n%s;

    ll b = c/s;

    ans += cnt*b;

    rep(i,n%s) ans += v[i];

    cout << ans << endl;

  }

  else {

    ll ans = 0LL;

    bool swi = true;

    vll vv;

    ll vs = v.size();

    rep(i,vs) {

      if(v[i]==a) swi = false;

      if(swi) {

        ans += v[i];

        n--;

      }

      else vv.push_back(v[i]);

    }

    ll s = vv.size();

    ll sum = 0LL;

    rep(i,s) sum += vv[i];

    ll b = n/s;

    ans += sum*b;

    rep(i,n%s) ans += vv[i];

    cout << ans << endl;

  }

  return 0;

}