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 scan = new Scanner(System.in);
        long n = scan.nextLong();
        long x = scan.nextLong();
        long m = scan.nextLong();
        x = x % m;
        Map<Long, Integer> M = new HashMap<>();
        List<Long> list = new ArrayList<>();
        M.put(x, 0);
        list.add(x);
        int i = 1;
        for (; i < n; i++) {
            x = x * x % m;
            if (M.containsKey(x)) break;
            M.put(x, i);
            list.add(x);
        }
        if (i == n) {
            long sum = 0;
            for (int j = 0; j < list.size(); j++) sum = sum + list.get(j);
            System.out.println(sum);
            return;
        }
        long ans = 0;
        int pos = M.get(x);
        for (i = 0; i < pos; i++) ans += list.get(i);
        n -= pos;
        int len = list.size() - pos;
        long sum = 0;
        for (int j = pos; j < list.size(); j++) sum = sum + list.get(j);
        long cnt = n / len;
        ans += sum * cnt;
        n %= len;
        for (i = 0; i < n; i++) {
            ans += list.get(pos + i);
        }
        System.out.println(ans);
    }
}
