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
//package src.com.jetman.atcoder;

import java.util.*;

/**
 * @description:
 * @author: Jetman
 * @create: 2020-08-29 14:39
 **/
public class Main {

    Scanner sc = new Scanner(System.in);

    long MOD = 998244353L;

    long dp[];

    private void slove() {

        long n = sc.nextLong();
        long x = sc.nextInt();
        long m = sc.nextInt();

        int[] flag = new int[(int)m+1];
        int index = 1;
        long tmp = x;
        flag[(int)x] = 1;
        long sum = x;
        int lun = 0;
        long start = 0;
        long[] allSum = new long[100003];
        allSum[1] = x;
        while (true) {
            if (index == n) {
                break;
            }
            tmp = (tmp*tmp)%m;
            index++;
            if (flag[(int)tmp] > 0) {
                lun = index - flag[(int)tmp];
                start = tmp;
                break;
            }
            flag[(int)tmp] = index;
            sum = (sum+tmp);
            allSum[index] = allSum[index-1] + tmp;
        }

        if ((long)index < n) {
            x = start;
            n = n-index+1;
            sum = sum + ((allSum[index-1] - allSum[index-lun-1]) * (n/lun));
            long nu = n%lun;
            tmp = x;
            for (int i = 0; i < nu; i++) {
                sum = (sum+(tmp));
                tmp = (tmp*tmp)%m;
            }
        }
        System.out.println(sum);



    }

    private void build(Map<Integer, List<Integer>> edge, int l, int r) {
        List<Integer> list = edge.getOrDefault(l, new ArrayList<>());
        list.add(r);
        edge.put(l,list);
    }


    public static void main(String[] args) {
        new Main().slove();
    }
}
