Million Dollar Man | CodeChef

Can anyone explain the algorithm to solve this problem?Thanks!

It is Matrix Exponentiation !! Search on Google

Refer to this discussion thread: Million Dollar Man.