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
# -*- coding: utf-8 -*-

N,X,M=map(int,input().split())

A=[0]*(M+1)
A[0]=X
D=[0]*(M+1)

s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if D[a] == 1:
        s=A.index(a)
        break
    else:
        A[i]=a
        D[a]=1

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    
    ans=0
    l=len(A)-s
    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    ans+=sum(A[s:(s+K)])


print(ans)
