While solving problems in SPOJ, I faced cases where I need to take Modulus of Big numbers like Fibonacci with 10^9 + 7 ( say MOD ). Now, consider the following case :
(Fib(n) + Fib(6*n-1)) / x
As Fib(n) cannot be stored in 64 bit for high n, we are forced to take modulus in every loop of calculating Fibonacci number using Matrix exponentiation. But the division by 'x' later does not give the correct result. That is
(Number/x) % MOD != (Number%MOD)/x generally.
So, in the above cases, is there any way to get correct result? That is Modulus have to be done before division and with that is it possible to get correct result?
This can be done using the Modular Inverse trick. The concept and the way to find that and also the usage is described with examples here.