Please help me with mod 10^9 +7|Not solved yet

i am doing a question where i have to get answer in modulo 10^9+7

Blockquote

for(j=0;j<5;j++)
{
num=num*i;
i--;
}
cout<<num<<endl;
return (num/120)%mod;

But the problem is that the value of num exceeds 10^9+7 and i am able to apply mod only after the whole loop is executed ie (return (num/120)%mod)

num*=i;

num%=mod;

i–;

just add num%=mod after n*=i;

It would give incorrect answer like this.
example

(36/3)%5 != (36%5)/3

I my case i have to divide num by 120 before returning.

If you know java, you can use BigInteger.

then you have to find the modular inverse of 120 and multiply it to num.
modular inverse of 120 = 120^(mod-2) % mod. mod is quite big so use logarithmic exponentiation. This only works if mod and 120 are co-prime in this case they are. If you have further doubts about modular inverse see this http://comeoncodeon.wordpress.com/2011/10/09/modular-multiplicative-inverse/

3 Likes

Understand Modular Arithmetic.

Here are two simple formulae:-

(ab)%m=((a%m)(b%m))%m

(a+b)%m=((a%m)+(b%m))%m

Problem with your code is – num is getting overflow, and then value is of absolutely no use.

Use these two in your code as –

for(j=0;j<5;j++)
{
    num=(num*i)%mod;
    i--;
}

cout<<num<<endl;
return (num/120)%mod;

Declaring num as long lor long long will be safer.

Modulo is not distributive over division. Which is why you cannot do % in your loop.

The correct approach is to find the modular multiplicative inverse of 120 as suggested in the comments.
I found this article/tutorial particularly helpful…

2 Likes