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

int main() {
	long long N;
	long long X, M;
	cin >> N >> X >> M;
	vector<long long> A, C(M, -1);
	A.push_back(X);
	C[X] = 0;
	long long ans = X;
	long long a = X;
	for (long long i = 1; i < N; i++) {
		a = a * a % M;
		ans += a;
		if (C[a] >= 0) {
			long long loop = 0;
			long long length = A.size() - C[a];
			for (long long j = C[a]; j < A.size(); j++) loop += A[j];
			ans -= a;
			ans += loop * ((N - i) / length);
			i += length * ((N - i) / length);
			for (long long j = 0; i + j < N; j++) ans += A[C[a] + j];
			i = N;
		}
		else {
			C[a] = i;
			A.push_back(a);
		}
	}
	cout << ans << endl;
}
