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.HashSet;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
    
        var sc = new Scanner(System.in);
    
        long n = Long.parseLong(sc.next());
        int x = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        
        var a = new long[m+1];
        var set = new HashSet<Long>();
        a[0] = x;
        set.add(a[0]);
        int r = -1;
        for(int i = 1; i <= m; i++){
            a[i] = a[i-1] * a[i-1] % m;
            if(!set.add(a[i])){
                r = i;
                break;
            }
        }
        int l = -1;
        for(int i = 0; i < m; i++){
            if(a[i] == a[r]){
                l = i;
                break;
            }
        }
        
        long ans = 0;
        long b = Math.min(n, l);
        for(int i = 0; i < b; i++){
            ans += a[i];
        }
        long n2 = n - l;
        long c = n2 / (r-l);
        for(int i = l; i < r; i++){
            ans += a[i] * c;
        }
        long d = l + (n2 % (r-l));
        for(int i = l; i < d; i++){
            ans += a[i];
        }
        System.out.println(ans);
    }
}