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 <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
int main(){
  long long N;
  cin>>N;
  long long X,M;
  cin>>X>>M;
  long long answer=0;
  long long A=X;
  if(N>M){
  long long rot[100000];
  for(int i=0;i<M;i++){
    rot[i]=A;
    answer+=A;
    A=(A*A)%M;
  }
  long long roop=1;
  long long S=rot[M-roop];
  while(A!=rot[M-roop]){
    roop++; S+=rot[M-roop];
  }
  answer+=((N-M)/roop)*S;
  for(long long i=0;i<(N-M)%roop;i++){
    answer+=A; A=(A*A)%M;
  }
  }
  else{
    for(int i=0;i<N;i++){
      answer+=A; A=(A*A)%M;
    }
  }
  cout<<answer<<endl;
  
  return 0;
}