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;

typedef long long ll;

ll m;

ll f(ll x) { return x*x%m; }

int main()
{
	ll n, x;
	scanf("%lld%lld%lld", &n, &x, &m);
	ll t = f(x), h = f(f(x));
	while (t != h) t = f(t), h = f(f(h));
	ll m = 0, l = 1;
	for (h = x; h != t; h = f(h), t = f(t), ++m);
	for (h = f(h); h != t; h = f(h), ++l);
	if (n <= m) {
		ll ans = x;
		while (--n) x = f(x), ans += x;
		printf("%lld\n", ans);
	}
	else {
		ll ans = 0, loop = 0;
		while (m--) ans += x, x = f(x), --n;
		for (int i = l; i > 0; --i) loop += x, x = f(x);
		for (int k = n%l; k--; ans += x, x = f(x));
		printf("%lld\n", ans+loop*(n/l));
	}
}