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;
typedef long long ll;
int main() {
	ll N, X, M;
	cin >> N >> X >> M;
	vector<int> hoge(M);
	vector<ll> sum = {0};
	ll x = X;
	int s, t;
	for (int i = 1; ; ++ i) {
		sum.push_back(sum.back() + x);
		if (hoge[x]) {
			s = hoge[x];
			t = i;
			break;
		}
		hoge[x] = i;
		x = x*x % M;
	}
	if (N < (int)sum.size()) {
		cout << sum[N] << endl;
		return 0;
	}
	ll k1 = (N - (s-1)) / (t - s);
	ll k2 = (N - (s-1)) % (t - s);
	cout << sum[s-1] + (sum[t-1]-sum[s-1]) * k1 + (sum[s-1+k2]-sum[s-1]) << endl;
}
