Can someone please tell me the algorithm I should use to solve this problem. My algorithm is giving TLE error.

Fast Matrix Exponentiation will be used to reduce the complexity to O(N^3*logK).

Fast Matrix Exponentiation will be used to reduce the complexity to O(N^3*logK).