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())

pt = [[0] * (M+100) for i in range(70)]
to = [[0] * (M+100) for i in range(70)]
for i in range(M+1):
    to[0][i] = (i*i) % M
    pt[0][i] = i

for i in range(65):
    for j in range(M+1):
        to[i+1][j] = to[i][to[i][j]]
        pt[i+1][j] = pt[i][j] + pt[i][to[i][j]]

ans = 0
for i in range(60):
    if (N>>i)&1:
        ans += pt[i][X]
        X = to[i][X]

print(ans)
