SPOJ — FRSKH
The problem requires to efficiently compute
The constraints are:
I have solved the easier version with constraint on 
and same constrains on 
M can be optimized using Pisano Period
N can be optimized using Fast Doubling/Matrix Exponentiation
The issue is constraint on K, which I cant figure a way to optimize. How can we resolve this issue?
Hello. This problem is actually harder than I thought and even algorithm is not deterministic. Here you can find editorial (page 68): http://www.bubblecup.org/Content/Media/Booklet2013.pdf