Russian Peasant Exponentiation is an efficient algorithm for computing powers using repeated squaring and multiplication, reducing computational complexity. It showcases the elegance of binary operations in simplifying seemingly complex problems. Betbhai9 id

1. Conver k into binary then do multiplication
2. Use mod to keep the value inside the default int range for best performance

Python code:

def solve(a, b, k, m):

    def mul(r1, i1, r2, i2):
        return (r1 * r2 - i1 * i2) % m, (r1 * i2 + r2 * i1) % m

    k2 = bin(k)[2:][::-1]

    # dp_i := (a + bj) ^ (2*i), i is index, j is image unit
    dp = (a, b)
    dpi = 0 
    
    real, imag = 1, 0
    for n in range(len(k2)):
        if k2[n] == '1':
            while n != dpi :
                dpi += 1
                dp = mul(*dp, *dp)
            real, imag = mul(real, imag, *dp)
    return real, imag

The problem relates to the Binary and Modular exponentiation. This requires the knowledge of complex number multiplication as well

Python: This solution works for values of k which do not lead to overflow when calculating: a^k and similarly large values.

def solve(a, b, k, m):
    complex_num = complex(a, b) ** k
    lst = map(int, [complex_num.real, complex_num.imag])
    return list(map(lambda x: x % m, lst))

Do not bother using Python3, use PyPy3 as your language. Otherwise you will get test timeouts.