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>
#include <algorithm>
#include <utility>
using namespace std;

typedef long long ll;

int main () {
	ll N;
	ll X, M;
	pair <int, ll> p[100001];
	cin >> N >> X >> M;
	for (int m=0; m<M; m++) {
		p[m].first = p[m].second = -1;
	}
	ll tmp = 0, ans;
	bool flag = true;
	ll i;
	for (i=0; i<N&&flag; i++) {
		tmp += X;
		p[X].first = i;
		p[X].second = tmp;
		X = X*X;
		X %= M;
		flag = (p[X].first == -1);
	}
	if (i==N) {
		ans = tmp;
	} else {
		ll steps = i - p[X].first;
		ll cnts = (N-i)/steps;
		ll v = (N-i)%steps;
		ll diff = tmp - p[X].second + X;
		for (ll j=0; j<v; j++) {
			tmp += X;
			X = X*X;
			X %= M;
		}
		ans = tmp + diff*cnts;
	}
	cout << ans << endl;
	return 0;
}