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 int ll;
typedef long double ld;
const int maxn=2E5+5;
ll n,x,m,ans;
ll a[maxn],sum[maxn];
inline ll f(ll x,ll m)
{
	return (x%m)*(x%m)%m;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>x>>m;
	a[x]=1;
	sum[1]=x;
	ans=x;
	for(ll now=x,i=2;i<=n;++i)
	{
		now=f(now,m);
		if(a[now])
		{
			ll len=i-a[now];
			ll left=n-i+1;
			ans+=(sum[i-1]-sum[a[now]-1])*(left/len);
			ans+=(sum[a[now]-1+(left%len)]-sum[a[now]-1]);
			break;
		}
		ans+=now;
		a[now]=i;
		sum[i]=sum[i-1]+now;
	}
	cout<<ans<<endl;
	return 0;
}
