Finally a problem where we need a little bit of math to solve it. It is called Summing the N series, and when I say a little bit, I mean only a little bit. The problem reads
You are given a sequence whose term is
You have to evaluate the series
Find .
Bruteforce solution to Summing the N series
We could try to just bruteforce a solution like this
sum = 0
for i in range(1, n+1):
sum += i*i - (i-1)*(i-1)
return sum % 1000000007
However, as n can go up to 10^16, that is not really a viable solution and when I tried I got a timeout on most of the problems evaluated. So lets look at the series.
Expanding the series
If we write out the last few terms of we get
As we can see the terms cancel out so we only have the first term of minus the last term of when summing the whole series. However the last term of . Therefore we end up with
and thus we can write the code as
return n*n % 1000000007
