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;
#define ll long long int
ll mod=998244353;
int main()
{
	ll i,j,k,m,n,t,x;
	cin>>n>>x>>m;
	ll ar[100001];
	ar[0]=x;
	map<ll,ll> mp;
	mp[x]=1;
	ll ans=x,c1=1;
	for(i=1;i<n;i++)
	{
		x=ar[i-1]*ar[i-1];
		x%=m;
		if(mp[x]) break;
		mp[x]++;
		c1++;
		ar[i]=x;
		ans+=x;
	}
	n-=c1;
	ll s=0;
	for(j=0;j<c1;j++)
	if(ar[j]==x) break;
	ll ctr=0;
	ll pos=j;
	for(;j<c1;j++)
	{
		s+=ar[j];
		ctr++;
	}
	ans+=(n/ctr)*s;
	n%=ctr;
	i=pos;
	while(n--)
	{
		ans+=ar[i];
		i++;
	}
	cout<<ans;
}