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) = 2Can somebody guide me in the right direction.
$\endgroup$ 61 Answer
$\begingroup$You can do the mod any time you like, before multiplication or after.
For another thing $4*5\equiv 0\pmod{10}$, not 2.
For example $16*12\equiv 192\equiv 2\pmod{10}$ and also
$16*12\equiv (10+6)*(10+2)\equiv 6*2\equiv 12\equiv 2\pmod{10}$
It's always advisable to mod before you multiply, as it will keep the numbers as small as possible.
$\endgroup$ 2
