import sys readline=sys.stdin.readline from collections import defaultdict import math def LCM(n,m): if n or m: return abs(n)*abs(m)//math.gcd(n,m) return 0 def Permutation_Product(x,n,f): lst=[] dct={} idx=0 cur=x while True: if cur in dct.keys(): loop_begin=dct[cur] loop_end=idx break else: lst.append(cur) dct[cur]=idx cur=f(cur) idx+=1 if loop_end-1>=n: return lst[n] n-=loop_begin loop_length=loop_end-loop_begin lst=lst[loop_begin:] return lst[n%(loop_length)] def Totient(N,mod): retu=N primes=list(Factorize(mod).keys()) l=len(primes) dp_popcount=[0]*(1<=1 factors=defaultdict(int) for p in range(2,N): if p**2>N: break while N%p==0: factors[p]+=1 N//=p if N!=1: factors[N]+=1 return factors A,N,M=map(int,readline().split()) mod=1 MM=M while MM>=2: mod=LCM(mod,MM) for p in Factorize(MM): MM=MM*(p-1)//p ans=Permutation_Product(1,N,lambda x:pow(A,x,mod))%M print(ans)