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<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll n,x,m,ans,tp;
int d[100001],a[100001];
int main(){
	cin>>n>>x>>m;
	d[x]=1,ans=x,a[1]=x;
	for(int i=2;i<=n;i++){
		x=x*x%m;
		if(d[x]){
			ans=0;
			for(int j=1;j<d[x];j++) tp+=a[j];
			for(int j=d[x];j<i;j++) ans+=a[j];
			n-=d[x]-1;
			ans*=(n/(i-d[x]));
			for(int j=1;j<=n%(i-d[x]);j++) ans+=a[d[x]-1+j];
			cout<<ans+tp;
			return 0;
		}
		else d[x]=i,ans+=x,a[i]=x;
	}
	cout<<ans;
}