백준 1629: 곱셈 - 모듈러 연산(Python/파이썬)

처음에 dp를 값 다 저장하는 방식으로 구현했다가 시간 초과 났던.....

import sys
input = sys.stdin.readline

A, B, C = map(int, input().split())

def mod(num, power, deno):
    remainder = num % deno
    if power == 0:
        return 1

    if power % 2: # 홀수면
        half = mod(num, power//2, deno)
        return (half * half * remainder) % deno
    else: # 짝수면
        half = mod(num, power//2, deno)
        return (half * half) % deno

print(mod(A, B, C))