Быстрое возведение в степень по модулю

def pow_h(base, degree, module):
    degree = bin(degree)[2:]
    r = 1
 
    for i in range(len(degree) - 1, -1, -1):
        r = (r ** 2) % module
        r = (r * base ** int(degree[i])) % module
 
    return r

 r = (r * base ** int(degree[i])) % module
 base = (base ** 2) % module

def power_mod(x:int, pow:int, mod:int):
    assert type(x) is int
    assert type(pow) is int and pow >= 0
    assert type(mod) is int
    res = 1
    pow_res = 0
    while pow_res < pow:
        pow_res_1 = 2
        res1 = x
        while pow_res + pow_res_1 <= pow:
            res1 = (res1 * res1) % mod
            pow_res_1 *= 2
        pow_res_1 //= 2
        res = (res * res1) % mod
        pow_res += pow_res_1
    return res % mod

base, exp, mod = map(int, input().split())
pow(base, exp, mod)

def fast_exp_mod(number, exp, n):
    i = 1
    result = number
    while 2 * i < exp:
        result = (result ** 2) % n
        i = i * 2
    while i:
        result_1 = number
        exp = exp - i
        i = 1
        while 2 * i < exp:
            result_1 = (result_1 ** 2) % n
            i = i * 2
        result = (result * result_1) % n
        if i == 1:
            break
    return result

def fast_exp_mod(number, exp, n):   
    i = 1
    exp = int(exp)
    result = number
    while 2 * i < exp:
        result = (result ** 2) % n
        i = i * 2
    while i:
        if exp == 2 * i:
            result = (result ** 2) % n
            break
        result_1 = number
        exp = exp - i
        i = 1
        while 2 * i <= exp:
            result_1 = (result_1 ** 2) % n
            i = i * 2
        result = (result * result_1) % n
        if i == 1:
            break
    return result