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;

int main(){
	long long n,x,m;
	cin >> n >> x >> m;
	vector<long long> ar;
	set<long long> st;
	ar.push_back(x);
	st.insert(x);
	long long nx = (x*x)%m;
	while(!st.count(nx)){
		ar.push_back(nx);
		st.insert(nx);
		nx = (nx*nx)%m;
	}
	long long l;
	for(l=0;l<ar.size();l++){
		if(ar[l] == nx){
			break;
		}
	}
	long long ans = 0;
	for(int i=0;i<min(n,l);i++){
		ans += ar[i];
	}
	n -= min(n,l);
	long long sum = 0;
	int left = n%(ar.size()-l);
	for(int i=0;i<(ar.size()-l);i++){
		if(i < left){
			ans += ar[i+l];
		}
		sum += ar[i+l];
	}
	ans += (n/(ar.size()-l))*sum;
	cout << ans << '\n';
}