### fast modular multiplication method

I was reading about Fast modulo multiplication.Suppose we have a base b and an exponent e which may be very large.

Now we want to calculate Ans = b^e.

Now basically what we do is we select a large prime no. like (10^9 + 7) as given in below code snippet to ensure the calculations are kept within limit and hence faster result.

i.e

Mod = 10^9 + 7

Ans = b^e%Mod

But can somebody clarify that wouldn't yield unintended/wrong output as the actual output may be larger than is Modulus value.

`long long int fast_exp(int base, int exp)
`

{

if(exp==1)

return base;

else

{

if(exp%2 == 0)

{

long long int base1 = pow(fast_exp(base, exp/2),2);

if(base1 >= 1000000007)

return base1%1000000007;

else

return base1;

}

else

{

long long int ans = (base* pow(fast_exp(base,(exp-1)/2),2));

if(ans >= 1000000007)

return ans%1000000007;

else

return ans;

}

}

}

## Answers

Yeah...we can't represent values greater than mod value in normal ways that's why we use mod value for checking the answers. ..

If a problem says give answer modulo 99, then in case your answer is coming to be 100, then you should output 1 for passing in the judge. ..