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;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final long N = sc.nextLong();
        final int X = sc.nextInt();
        final int M = sc.nextInt();
        
        if (X == 0) {
            System.out.println(0);
            return;
        }
        
        int A = X;
        
        // 数列の累積和を記録する。
        long[] sum = new long[M + 1];
        sum[0] = A;
        
        // その項が数列の何番目（0開始）に現れたかを記録する。
        int[] idx = new int[M + 1];
        idx[A] = 0;
        
        int i = 1;
        for (; i < N; i++) {
            long B = A;
            A = (int) (B * B % M);
            
            if (A == X || 0 < idx[A]) {
                break;
                
            } else {
                sum[i] = sum[i - 1] + A;
                idx[A] = i;
            }
        }
        
        if (i == N) {
            System.out.println(sum[i - 1]);
            return;
        }
        
        int idxRepeatStart = idx[A];
        
        int lenPrefix = idxRepeatStart;
        int lenRepeat = i - idxRepeatStart;
        long numRepeats = (N - lenPrefix) / lenRepeat;
        int lenSuffix = (int) (N - lenPrefix - lenRepeat * numRepeats);
        
        long sumPrefix = 0 < idxRepeatStart ? sum[idxRepeatStart - 1] : 0;
        long sumRepeat = sum[i - 1] - sumPrefix;
        long sumSuffix = 0 < lenSuffix ? sum[idxRepeatStart + lenSuffix - 1] - sumPrefix : 0;
        
        long answer = sumPrefix + sumRepeat * numRepeats + sumSuffix;
        System.out.println(answer);
    }
}
