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>
#define MAXN 100000+10

using namespace std;

long long n;
long long MOD;
long long Ans[MAXN];
long long S[MAXN];

int main()
{
	long long Now;
	cin>>n>>Now>>MOD;
	memset(Ans,-1,sizeof(Ans));
	Ans[Now] = 1;
	S[1] = Now;
	//long long Count = Now;
	for(int i=2;i<=n;i++)
	{
		Now = Now*Now%MOD;
		S[i] = S[i-1] + Now;
		if(Ans[Now]!=-1)
		{
			long long Re = S[Ans[Now]-1];
			long long XHJ = S[i] - S[Ans[Now]];
			long long CD = i - Ans[Now];
			n -= Ans[Now] - 1;
			Re += XHJ * (n/CD);
			Re += S[Ans[Now]+n%CD-1] - S[Ans[Now]-1];
			cout<<Re;
			return 0;
		}
		Ans[Now] = i;
	}
	cout<<S[n];
	return 0;
}
