I'm trying to solve some problems on interviewstreet. For some problems they mention
As the answers can be very big, output them modulo 1000000007.
How can I compute
a*b mod N where N is a large number like 1000000007.
I thought of using
(a mod N) * (b mod N) = (a*b mod N)
but I reckon performing this wouldn't work. Example :
a=4, b=5 and N=10 (4 mod 10) * (5 mod 10) = 20 whereas (4*5 mod 10) = 2
Can somebody guide me in the right direction.