How to correctly use Mod 10^9+7
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
(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