MPOW - Power of matrix (SPOJ Problem)

Simple problem : We’re given a square matrix M and a positive integer power N, and we’ve been asked to compute M raised to the power N.

Simple Matrix Exponentiation should do the job.

But my solution goes TLE : https://ideone.com/9dQ4hd

But I’m not sure why it is so. The worst case time complexity is O(d^3 . logN), where d denotes the dimensions of the square matrix.

Where am I going wrong in my code? Any kind of help would be appreciated.

UPDATE:

If someone comes across this type of issue in future which is highly unlikely.

Just use a statically typed compiled language like C++. Unlike codeforces, SPOJ doesn’t provide pypy3 compiler, so that sucks. If someone knows how to optimize the code, just let me know. I’d love to see it.

My Submission : https://ideone.com/tHLsrE