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