I found two C# solutions: with multithreading — Accepted and without multithreading — TLE. The author of the solution uses Parallel.For in the functionMultiplyMatrixPow, due to which it achieves success. Question: how many cores can we load on codeforces servers when testing our solution?

UPD: In first program author takes remainder from integer division 3 times, in second program just 1 times. So, this is not multithreading hack.