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(" "))
q = [-1] * (M + 1)
A = X
i = 0
su = []
p1 = 0
p2 = 0
while q[A] == -1:
    q[A] = i
    su.append(A)
    A = (A * A) % M
    i += 1

if N == len(su):
    print(sum(su))
else:
    r = q[A]
    r2 = (N - r) % (i - r)

    ans1 = sum(su[0:r])
    ans2 = sum(su[r:r + r2])
    ans3 = sum(su[r::])

    print(ans1 + ans2 + ans3 * ((N - r) // (i - r)))