The fastest way is to use matrix exponentiation and it is quite simple to understand. The algorithm is O(log n), yes it is that fast!. I got AC with Python 2.7 with 0.046s. Python has an added advantage for this problem since its Integer type can be as big as the RAM of the device being used. With c++ you can still get answers fast, using matrix exponentiation, but the answers are not precise enough, and leads to WA.

Edited by author 29.07.2015 15:42