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 <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int x,m,a[100005],l,r;
long long f[100005],ans,sum,n;

int main()
{
	scanf("%lld%d%d",&n,&x,&m);
	f[1]=x%m;a[f[1]]=1;
	for (int i=2;i<=n;i++) {
		f[i]=f[i-1]*f[i-1]%m;
		if (a[f[i]]) {
			l=a[f[i]];r=i;break;
		}else a[f[i]]=i;
	}
	if (!r) {
		for (int i=1;i<=n;i++) ans+=f[i];
	}else {
		for (int i=1;i<l;i++) ans+=f[i];
		for (int i=l;i<r;i++) sum+=f[i];
		ans+=sum*((n-l+1)/(r-l));
		int t=(n-l+1)%(r-l);
		for (int i=1;i<=t;i++) ans+=f[i+l-1];
	}
	printf("%lld\n",ans);
	return 0;
}