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
N,X,M=map(int,input().split())

seen=[-2]*M
seen[X]
A=[X]
i=1
while(i<N):
    T=A[-1]**2%M
    if seen[T]!=-2:
        Roop=i-seen[T]
        Left,Right=seen[T],i
        break
    A.append(T)
    seen[T]=i
    i+=1

if i==N:
    print(sum(A))
    exit()

Roopsum=0
for i in range(Left,Right):
    Roopsum+=A[i]

Rest=N-len(A)

ans=sum(A)

ans+=Rest//Roop*Roopsum

for i in range(Rest%Roop):
    ans+=T
    T=T**2%M
print(ans)