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;

/**
 * @author kep
 * @date 2019-10-17
 */
public class Main {

    private static int[] vis = new int[100005];
    private static long[] sum = new long[100005];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long x = scanner.nextLong();
        long mod = scanner.nextLong();
        long ans = 0;
        int index = 1;
        int startIndex = -1;
        for(;index<=n;index++){
            if(vis[(int)x] != 0){
                startIndex = vis[(int)x];
                break;
            }
            vis[(int)x] = index;
            sum[index] = sum[index-1]+x;
            ans += x;
            x = (x*x)%mod;
        }
        if(n >= index){
            n = n - index + 1;
            ans = ans + (n/(index-startIndex))*(sum[index-1]-sum[startIndex-1]);
            if(n%(index-startIndex) != 0){
                int xx = (int)(n%(index-startIndex));
                ans = ans + sum[startIndex+xx-1] -sum[startIndex-1];
            }
        }
        System.out.println(ans);
    }



}