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 in = new Scanner(System.in);
        long n = in.nextLong();
        long x = in.nextLong();
        long m = in.nextLong();
        List<Long> foundList = new ArrayList<>();
        Set<Long> foundSet = new HashSet<>();
        
        long a = x;
        long ans = a;
        foundList.add(Long.MIN_VALUE); // 0番目はダミーの値。便宜上。
        foundList.add(a);
        foundSet.add(a);
        for(long i=2; i<=n; i++) {
            long next = (a*a)%m;
            foundList.add(next);
            if(foundSet.contains(next)) {
                // ループ検出
                // 何番目からi番目までがループであるのかを知る
                int loopStart = foundList.indexOf(next); // これがintに収まるということは未証明
                int loopEnd = (int)i-1;
                long loopCycle = loopEnd - loopStart + 1;
                long loopLength = n - loopStart + 1;
                long loopMod = loopLength % loopCycle;
                long loopCount = (loopLength - loopMod) / loopCycle;
                loopCount--; // ループ1回分は既にansに足されているので
                
                long loopSum = 0;
                for(int j=loopStart; j<=loopEnd; j++) {
                    loopSum += foundList.get(j);
                }
                if(loopCount>0) {
                    ans += loopCount*loopSum;
                }
                for(int j=loopStart; j<loopStart+loopMod; j++) {
                    ans += foundList.get(j);
                }
                break;
            }
            else {
                foundSet.add(next);
            }
            ans += next;
            a = next;
        }
        System.out.println(ans);
    }
}
