def power(a, b):
if b==1: # base condition
return a % C
val = pow(a, b//2)
if b%2==0: return val*val % C
else: return val*val*a % C
A,B,C = map(int, input().split())
print(power(A, B))
Recursion
A**B mod C 를 구하는 문제
B==1이면 base condition으로 재귀가 종료
아니면 pow(a, b//2)로 재귀 후
B가 홀수 짝수인지에 따라 리턴값이 다름