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.

C# doesnt take care of negative module result:

class ComplexInt
{
    public int mod;
    public int a, b;
    public ComplexInt() { a = 1; b = 0; mod = int.MaxValue; }
    public ComplexInt(int _a, int _b, int _mod = int.MaxValue)
    { mod = _mod; a = (_a % mod + mod) % mod; b = (_b % mod + mod) % mod; }
    public static ComplexInt operator *(ComplexInt x, ComplexInt y)
        => new ComplexInt((int)(((long)x.a * y.a - (long)x.b * y.b) % x.mod),
                          (int)(((long)x.a * y.b + (long)x.b * y.a) % x.mod), x.mod);
}





public static List<int> solveRussPeas(int a, int b, long k, int m)
{
    var p = powRussPeas(new ComplexInt(a, b, m), k);
    return new List<int> { p.a, p.b };
}
public static ComplexInt powRussPeas(ComplexInt x, long k)
{
    ComplexInt p = k % 2 == 0 ? new ComplexInt(1, 0, x.mod) : x;
    while ((k >>= 1) > 0)
    {
        x *= x;
        if (k % 2 == 1)
            p *= x;
    }
    return p;
}

...need to take care yourself