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;

vector <long long> path;
int vis[100010];

int main () {
	memset(vis, -1, sizeof(vis));
	long long n, x, mod; cin >> n >> x >> mod;
	while (vis[x] == -1) {
		vis[x] = path.size();
		path.push_back(x);
		x = x * x % mod;
	}
	int pos = vis[x];
	long long ans = 0;
	int len = (int)path.size() - pos;
	long long k = (n - pos) / len, sum = 0;
	for (int i = 0; i < pos; i++) {
		ans += path[i], n--;
		if (n == 0) goto END;
	}
	for (int i = pos; i < path.size(); i++) {
		sum += path[i];
	}
	ans += k * sum, n %= len;
	for (int i = pos; i < pos + n; i++) {
		ans += path[i];
	}
	END:;
	cout << ans << endl;
	return 0;
}
