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 int MOD = 998244353;
    
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        Random random = new Random();
        long n = sc.nextLong();
        int x = sc.nextInt();
        int m = sc.nextInt();
        
        // ans:
        // array = {2,4,<16,256,471,620>}について、
        // 「i=0からスタートし、">"まで来たら"<"に戻る」ルールで、
        // 操作「今いるarray[i]の値を加算し、i++する」をn回したときの合計
        
        // array: a[i+1] = (a[i] * a[i]) % m
        
        // how: ρの形で考えて3パターンでそれぞれ集計する。
        
        Set<Integer> set = new HashSet<Integer>();
        List<Integer> list = new ArrayList<Integer>();
        set.add(x);
        list.add(x);
        int now = x;
        int last = 0;
        for (long i = 0; i < n; i++) {
            now = (int)((long)now * now % m);
            if (set.contains(now)) {
                last = now;
                break;
            } else {
                set.add(now);
                list.add(now);
            }
        }
        
        int loop_idx = 0;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == last) {
                loop_idx = i;
            }
        }
        
        long ans = 0;
        
        // [start, loop始点)
        for (int i = 0; i < loop_idx; i++) {
            ans += list.get(i);
        }
        n -= loop_idx;
        
        // [loop始点, loop終点] * 何周できるか
        long loop_sum = 0;
        for (int i = loop_idx; i < list.size(); i++) {
            loop_sum += list.get(i);
        }
        long len = list.size() - loop_idx;
        long block = n / len;
        ans += loop_sum * block;
        n %= len;
        
        // [loop始点, 残りの移動回数]
        for (int i = loop_idx; i < loop_idx + n; i++) {
            ans += list.get(i);
        }
        
        System.out.println(ans);
    }
}