How to correctly use Mod 10^9+7

Question

In Java, I need to calculate sum of squares of first n numbers i.e.

1^2 + 2^2+ 3^2+.....+n^2

which is

n(n+1)(2n+1)/6   

OR

n^3/3 + n^2/2 + n/6

Then I need to calculate another value

n*(n-1/2)^2

As n is going to be very big answer can be "answer%M" where M is 10^9+7.

I am not able to understand at which point of calculation I should do operation %M. e.g.

n%M * (n+1)%M (2n+1)%M /  6 

or

(n(n+1)(2n+1)/6)%M

Can you please help me here. Also in general please provide the guidelines for using %M;so that I can decide it next time onward.

Answer 1

(n(n+1)(2n+1)/6)%M is correct in theory and n%M * (n+1)%M * (2n+1)%M / 6 is incorrect.

If n is large, the intermediate calculations of (n(n+1)(2n+1)/6) will overflow your integer type, so the first method is also unsatisfactory.

The general solution for computing a*b/c % M would be to compute the modular inverse of c mod M (say c') and then compute: ((a%M * b%M)%M * c')%M

Here, it's a little simpler as you're dividing by a constant (6) and can find and strike out factors of 2 and 3 in the three terms. Something like this in pseudocode:

n1 := n
n2 := n+1
n3 := 2n+1
if n1 % 2 == 0 { n1 /= 2 } else { n2 /= 2 }
if n1 % 3 == 0 { n1 /= 3 } else if n2 % 3 == 0 { n2 /= 3 } else { n3 /= 3}
return (((n1 % M) * (n2 % M)) % M * (n3 % M)) % M