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 sc = new Scanner(System.in);
        long N = sc.nextLong();
        long X = sc.nextLong();
        long M = sc.nextLong();

        Map<Long,Integer> history = new HashMap<>();

        int newer, older;
        long a = X;
        long[] sum = new long[120000]; // sum[i] : sigma[0,i] a[i]
        for(int i=1;; i++){
            sum[i] = sum[i-1] + a;
            if(history.containsKey(a)){
                newer = i;
                older = history.get(a);
                //System.out.printf("%d : %d, %d\n", a, older, newer);
                break;
            }
            history.put(a, i);
            a = (a*a)%M;
        }

        if(newer >= N){
            System.out.println(sum[(int)N]);
            return;
        }
        long periodCount = (N-newer) / (newer-older);

        long periodSum = sum[newer] - sum[older];

        long restartPoint = newer + (newer-older) * periodCount;
        long s = sum[newer] + periodSum * periodCount;

        //System.err.printf("sum[1, %d] = %d\n", restartPoint, s);

        for(long n=restartPoint+1; n<=N; n++){
            a = (a*a) % M;
            s += a;    
        }

        System.out.println(s);
        
    }
}