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

ll N;
int X, M;

vector<ll> A;
map<ll, ll> idxs;
int main()
{
	cin>>N>>X>>M;
	A.push_back(0);
	A.push_back(X);
	idxs[X] = 1;
	ll last = X;
	ll ans = X;
	for(ll i = 2; i <= N; ++i)
	{
		last = last * last % M;
		if(idxs.count(last) != 0)
		{
			ll idx = idxs[last];
			ll len = i - idx;
			ll loop = (N - i + 1) / len;
			ll rest = (N - i + 1) - len * loop;
			ll tmp = 0;
			for(ll j = idx; j < i; ++j)
			{
				tmp += A[j];
			} 
			ans += loop * tmp;
			for(ll j = 0; j < rest; ++j)
				ans += A[idx+j];
			cout<<ans<<endl;
			return 0;
		}
		idxs[last] = i; 
		A.push_back(last);
		ans += last;
	}
	cout<<ans<<endl;
}
