Confused about MODULO 10^9 + 7

I have a stupid doubt if in question we have given range of values upto 10^18 but the answer is accepted to be MODULO 10^9 + 7.
Then i have two choices:

  1. At each step i should take MODULO, despite the fact that number can be stored in long long int range.(shown by fun1)
  2. I should take MODULO only where the result is excepted to overflow range of data type.(shown by fun2)

which approach is correct and why ?

ll:long long int
ex:
void fun1(ll a,ll b)
{
a=a%M;
b=b%M;
ll c=(a+b)%M;
ll d=(c*a)%M;
cout<<d<<endl;
}

void fun2(ll a,ll b)
{

ll c=(a+b)%M;
ll d=(c*a)%M;
cout<<d<<endl;
}

fun1 is safer if a and b are of order 10^18,

Here’s how fun2 fails,
fun2(10^18,10^18)
c=~10^9
d=((10^9)(10^18))%MOD, overflow here! (better use ((c%M)(a%M))%M )

Nope one of them is not correct

If a and b are less than M i.e. a, b \leq 10^9+6 then a+b \leq (10^9+6)\cdot 2 and a*b \leq (10^9+6)^2 \sim 10^{18} therefore(a+b)%M and (a*b)%M will be correct and efficient. Modulo is a ‘heavy’ operation so use it as less as possible.

Usually, what we want to calculate is in terms of previously calculated ( and modulo’d ) elements. For example if you want to calculate the factorial of a number n, you can do

fact[0] = 1 
for( ll i=1; i<=n; ++i )
    fact[i] = (i*fact[i-1])%m;

Notice we did not have to do fact[i] = ((i%m)*(fact[i-1]%m))%m;

1 Like

Bcuz you know that fact[i-1] < m and i<m so there is no point of taking mod again. So in your functions as well if you are sure that a and b are less than m then no need for mod.