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;
typedef long long ll;
int main(){
  ll N,X,M,S;
  cin >> N >> X >> M;
  ll m[M],n[M+1];
  S=X;
  for(ll i=0;i<M;i++)m[i]=-1;
  m[X]=1;
  n[1]=X;
  for(ll i=2;i<=N;i++){
    X=(X*X)%M;
    if(m[X]!=-1){
      ll y=(N-i+1)/(i-m[X]);
      if(y>0){
        ll o=0;
        for(ll j=m[X];j<i;j++)o+=n[j];
        S+=o*y;
      }
      ll l=(N-i+1)%(i-m[X]);
      for(ll j=m[X];j<m[X]+l;j++)S+=n[j];
     cout << S;
      return 0;
    }
    m[X]=i;
    n[i]=X;
    S+=X;
  }
  cout << S;
}