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();
        int k=sc.nextInt();
        int m=sc.nextInt();
        int cnt=0;
        TreeMap<Long,Integer> tmap=new TreeMap<>();
        long prod=1L*k;
        long ans=0;
        int ind=-1;
        for(int i=0;i<Math.min(n,m);i++)
        {
            tmap.put(prod%m,i);
            ans=ans+prod%m;
            cnt++;
            prod*=prod;
            prod%=m;
            if(tmap.containsKey(prod))
            {
                ind=tmap.get(prod);
                break;
            }
        }
        if(cnt==n)
        System.out.println(ans);
        else if(cnt<n)
        {
            long div=0;
            long sum=0;
            for(Map.Entry<Long,Integer> me:tmap.entrySet())
            {
                if(me.getValue()>=ind)
                {
                    sum=sum+me.getKey();
                    div++;
                }
            }
            ans=ans+sum*((n-cnt)/div);
            int cnt1=(int)((n-cnt)%div);
            for(Map.Entry<Long,Integer> me:tmap.entrySet())
            {
                if(me.getValue()>=ind&&me.getValue()<ind+cnt1)
                {
                    ans=ans+me.getKey();
                }
            }
            System.out.println(ans);
        }
    }
}