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?