ive been trying to solve this problem since yesterday night . however i could only come up with an O(d*d*k) solution.

this however wont work due to Memory and time limits.

I also looked at one of the solved solutions by rajat1603 solution link

Could someone explain how matrix exponentiation could be used in these type of problems ?

help would be greatly appreciated :D