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
import java.util.Scanner;

public class Main {
	static long[] calcLoopNum(long X , long M){
		long sum = 0;
		int vis[] = new int[(int)M + 1];
		int ln = 0;
		while(vis[(int)X] != 1){
			++ln;
			sum += X;
			vis[(int)X] = 1;
			X = (X * X) % M;
		}
		return new long[]{ln, sum};
	}
	static long solve(long N , long X , long M){
		if(N <= 2 * M){
			long ret = 0;
			for(int i = 0 ; i < N ; ++i){
				ret += X;
				X = (X * X) % M;
			}
			return ret;
		}
		long ret = 0;
		int vis[] = new int[(int)M + 1];
		long n = 0;
		while(vis[(int)X] != 1){
			++n;
			ret += X;
			vis[(int)X] = 1;
			X = (X * X) % M;
		}
		N -= n;
		long loop[] = calcLoopNum(X, M);
//		System.out.println(N+" "+ret+" "+X+" "+loop[0]+" "+loop[1]);
		ret += loop[1] * (N / loop[0]);
		N -= loop[0] * (N / loop[0]);
//		System.out.println(N+" "+ret+" "+X+" "+loop[0]+" "+loop[1]);
		ret += solve(N , X , M);
		return ret;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long X = sc.nextLong();
		long M = sc.nextLong();
		long r = solve(N , X , M);
		System.out.println(r);
	}
}
