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 len=0;
ll a[100004],d[100004];
ll N;
ll M;
int vis[100004],st;
int main(){
	len=1;
	cin>>N>>a[1]>>M;
	d[1]=a[1];
	while(1){
		len++;
		a[len]=a[len-1]*a[len-1]%M;
		if(vis[a[len]]){
			st=vis[a[len]];
			len--;
			break;
		}
		vis[a[len]]=len;
		d[len]=d[len-1]+a[len];
	}
	ll ans=0;
	for(int i=1;i<st;i++){
		N--;
		ans+=a[i];
	}
	int lenl=len-st+1;
	ans+=N/lenl*(d[len]-d[st-1]);
	cout<<ans+d[N%lenl+st-1]-d[st-1];
}