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 Int int64_t

using namespace std;

int main() {
	Int N, X, M;
	cin >> N >> X >> M;

	map<Int, Int> mp;
	Int cnt = 1;
	Int A = X;
	vector<Int> sum(1000000, 0);
	Int ans = 0;
	while (cnt <= N) {
		sum[cnt] += sum[cnt - 1];
		if (mp.count(A) == 0) {
			mp[A] = cnt;
			sum[cnt++] += A;
			A = A * A % M;
			continue;
		}

		Int idx = mp[A];
		sum[cnt] += A;
		A = A * A % M;
		
		Int S = sum[cnt] - sum[idx];
		Int n = cnt - idx;
		ans = sum[idx] + (N - idx) / n * S;
		for (Int i = 0; i < (N - idx) % n; ++i) {
			ans += A;
			A = A * A % M;
		}
		break;
	}
	if (cnt > N) { ans = sum[N]; }
	cout << ans << "\n";

	return 0;
}
