 # stropr problem python

As mentioned in the STROPR editorial, I’m calculating the coefficients by

(M+3)!/ (4! * (M-1)! ) = M*(M+1)(M+2)(M+3)/4!

So, here is my code link:

Here’s what I’m doing:
I’m going backwards from x.
Every loop, I calculate product = product * (M + extra) / (extra)
and then the total sum is stored in sums as sums = sums + Ax * product
and as the loop goes, the extra is incremented by one.
And then the output is sums % 1000000007

Subtasks 1 and 2 ran perfectly. But, it gave TLE in the 3rd subtask.
I don’t know where I’m making any mistake. I think that I’m using the least loops required to calculate the sum, but clearly I’m doing something wrong. Would someone please guide me in the right direction? Thanks, in advance.

The result can be a really huge number. So big that even multiplying 2 numbers gets slow.

You should have used the modulo in the intermediate calculations to keep the numbers small.

2 Likes

product = product * (M + extra) / (extra)
Here actually you should calculate the multiplicative inverse of 1/extra with respect to MOD(10**9 +7)