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;
#define INF 1LL<<62
#define inf 998244353
ll ans[500010]={};
int main() {
	ll n,a,k;
	cin>>n>>a>>k;
	map<ll,ll>q;
	ll now=a;
	q[a]++;
	ll cnt=1;
	ll ans=a;
	if(n==1){
		cout <<ans;
		return 0;
	}
	bool ro=false;
	ll rocnt=0;
	ll rozan=0;
	while(true){
		cnt++;
		now*=now;
		now%=k;
		q[now]++;
		ans+=now;
		if(q[now]==3){
			ll zan=n-cnt;
			ans+=zan/rozan*rocnt;
			zan%=rozan;
			cnt=n-zan;
			//cout <<cnt<<endl;
		}		
		if(cnt==n){
			cout <<ans<<endl;
			return 0;
		}		
		if(q[now]==2){
			ro=true;
		}
		if(ro){
			rocnt+=now;
			rozan++;
		}
		//cout <<now<<endl;
	}
	// your code goes here
	return 0;
}