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.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		long n = Long.parseLong(sa[0]);
		int x = Integer.parseInt(sa[1]);
		int m = Integer.parseInt(sa[2]);
		br.close();

		Set<Long> set = new HashSet<>();
		long ans = x;
		long now = x;
		int i = 1;
		set.add(now);
		for ( ; i < n; i++) {
			now = now * now % m;
			ans += now;
			if (!set.add(now)) {
				i++;
				break;
			}
		}

		long sum = 0;
		int d = 0;
		set.clear();
		for ( ; i < n; i++) {
			now = now * now % m;
			ans += now;
			if (!set.add(now)) {
				i++;
				break;
			}
			sum += now;
			d++;
		}
		if (i == n) {
			System.out.println(ans);
			return;
		}

		long r = n - i;
		ans += sum * (r / d);
		r %= d;
		for (int j = 0; j < r; j++) {
			now = now * now % m;
			ans += now;
		}
		System.out.println(ans);
	}
}
