[Python] 백준 1629번 곱셈, 13171 A | 분할 정복을 이용한 거듭제곱

A = int(input())
X = int(input())

arr = [A]
exp = 1
while True:
    exp *= 2
    if X < exp:
        break
    arr.append((arr[-1] ** 2) % 1000000007)
    
def decompose_bin(x):
    result = []
    power = 0
    
    while x > 0:
        if x % 2 == 1:
            result.append(power)
        x //= 2
        power += 1
        
    return result

def solution(A, X):
    X_bin = decompose_bin(X)

    ans = 1
    for b in X_bin:
        ans *= (arr[b])
    return ans % 1000000007
    
print(solution(A, X))

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

arr = [A]
exp = 1
while True:
    exp *= 2
    if B < exp:
        break
    arr.append((arr[-1] ** 2) % C)

def decompose_bin(x):
    result = []
    power = 0

    while x > 0:
        if x % 2 == 1:
            result.append(power)
        x //= 2
        power += 1

    return result

B_bin = decompose_bin(B)
ans = 1
for b in B_bin:
    ans *= arr[b]

print(ans % C)