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.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long X = sc.nextInt();
		int M = sc.nextInt();
		long prev = X, ans = X, x = 0;
		int st = -1, end = -1;
		long[] sum = new long[M+2];
		sum[0] = X;
		List<Long> l = new ArrayList<>();
		Set<Long> s = new HashSet<>();
		l.add(X);
		s.add(X);
		for(int i = 1; i < N; i++) {
			long mod = prev * prev % M;
			ans += mod;
			sum[i] = sum[i-1] + mod;
			if(!s.contains(mod)) {
				s.add(mod);
				l.add(mod);
			}
			else {
				x = mod;
				end = i;
				st = l.indexOf(mod);
				break;
			}
			prev = mod;
		}
		int T = end - st;
		if(end != -1 && end < N) {
			ans = (N - st) / T * (sum[end] - sum[st]);
			if(st != 0)
				ans += sum[st-1];
			if((N - st) % T != 0) {
				ans += sum[(int)((N - st) % T - 1) + st];
				if(st != 0)
					ans -= sum[st-1];
			}
		}
		System.out.println(ans);
	}

}