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

general
,
1

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)

2

num*=i;

num%=mod;

i–;

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

3

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.

4

If you know java, you can use BigInteger.

5

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
6

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.

7

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