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;

using lint = long long;

lint mod, N, X, L, R, arr[100004], rec[100004];

int main() {
	cin >> N >> X >> mod;

	arr[1] = X;
	rec[X] = 1;

	for (int i=2; ; i++) {
		arr[i] = (arr[i-1] * arr[i-1]) % mod;
		if (rec[arr[i]]) {
			L = rec[arr[i]];
			R = i;
			break;
		}
		rec[arr[i]] = i;
	}

	lint ans = 0;

	for (int i=1; i<=N and i<R; i++) {
		if (i < L) ans += arr[i];
		else ans += arr[i] * (long long)((N-L) / (R-L) + ((N-L) % (R-L) >= i-L));
	}

	cout << ans << '\n';
}