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;

const int N = 1e5 + 9;
 
int f[N][40];
long long s[N][40];
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long k; cin >> k;
	int x, n; cin >> x >> n;
	for (int i = 0; i < n; i++) f[i][0] = 1LL * i * i % n;
	for (int i = 0; i < n; i++) s[i][0] = i;
	for (int k = 1; k < 40; k++) {
		for (int i = 0; i < n; i++) {
			f[i][k] = f[f[i][k - 1]][k - 1];
			s[i][k] = s[i][k - 1] + s[f[i][k - 1]][k - 1];
		}
	}
	int cur = x;
	long long sum = 0;
	for (int i = 0; i < 40; i++) {
		if (k >> i & 1) {
			sum += s[cur][i];
			cur = f[cur][i];
		}
	}
	cout << sum;
    return 0;
}