from pip._vendor.distlib.compat import raw_input

A, N, M=map(int,raw_input().split())
memo={1:0}
res={0:1}
p=1
while  pow(A,p,M) not in memo:
    tmp=pow(A,p,M)
    memo[tmp]=memo[p]+1
    res[memo[tmp]]=tmp
    p=tmp
d=memo[p]+1-memo[pow(A,p,M)]
s=memo[pow(A,p,M)]
if s>=N:
    print(res[N])
else :
    print(res[((N-s)%d+s)])