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;
 
long long st[200010];
int vis[200010];
 
int main() {
	int x, m;
	long long n;
	scanf("%lld%d%d", &n, &x, &m);
	memset(vis, -1, sizeof(vis));
	long long ans = 0;
	int i;
	long long j;
	for (i = 0, j = x; vis[j] == -1; ++i, j = j * j % m)
		vis[j] = i, st[i] = j;
	if (n == vis[j]) {
		for (int k = 0; k < n; ++k)
			ans += st[k];
		printf("%lld\n", ans);
		return 0;
	}
	
	for (int k = 0; k <	vis[j]; ++k)
		ans += st[k];
	long long sum = 0;
	for (int k = vis[j]; k < i; ++k)
		sum += st[k];
	for (int k = 0; k < (n - vis[j]) % (i - vis[j]); ++k)
		ans += st[k + vis[j]];
	printf("%lld\n", ans + (n - vis[j]) / (i - vis[j]) * sum);
	return 0;
}