Let us denote by f(x, m) the remainder of the Euclidean division of x by m.

Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M). Find \displaystyle{\sum_{i=1}^N A_i}.

Constraints

* 1 \leq N \leq 10^{10}
* 0 \leq X < M \leq 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N X M


Output

Print \displaystyle{\sum_{i=1}^N A_i}.

Examples

Input

6 2 1001


Output

1369


Input

1000 2 16


Output

6


Input

10000000000 10 99959


Output

492443256176507
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll f(ll n, ll x, ll m){
  ll ref = x;
  ll now = x * x % m;
  int cnt = 1;
  vector<ll> d(m+1);
  d[0] = 0;
  while(now != x){
    d[cnt] = ref;
    ref += now;
    now = now * now %m;
    ++cnt;
  }
  ref = n/cnt *ref + d[n%cnt];
  return ref;
}

int main(){
  ll n, x, m;
  cin >> n >> x >> m;
  vector<bool> ok(m,true);
  ll cnt = 0;
  ll ans = 0;
  while(cnt < n){
    if(!ok[x]) break;
    ans += x;
    ok[x] = false;
    x = x*x % m;
    ++cnt;
  }
  ans += f(n-cnt,x,m);
  cout << ans << endl;
}