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
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
LL n,x,m,s[N],a[N];
int pos[N];
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>x>>m;
  pos[x]=1;s[1]=x;a[1]=x;
  for(int i=2;i<=n;i++){
    a[i]=(a[i-1]*a[i-1])%m;
    if(pos[a[i]]){
      LL last=n-i+1;
      LL duan=i-pos[a[i]];
      cout<<s[i-1]+(last/duan)*(s[i-1]-s[pos[a[i]]-1])+(-s[pos[a[i]]-1]+s[pos[a[i]]-1+(last%duan)])<<'\n';
      return 0;
    }else{
      pos[a[i]]=i;
    }
    s[i]=s[i-1]+a[i];
  }
  cout<<s[n]<<'\n';
  return 0;
}