stropr problem python

Here is the problem link:
link text

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:
link text

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.


product = product * (M + extra) / (extra)
Here actually you should calculate the multiplicative inverse of 1/extra with respect to MOD(10**9 +7)
link text
Hope it helps, cheers!

1 Like

First no need to store the answer of each test case in out list , directly print it in the loop itself,

And multiplying big numbers can get slow , so use mod the sum by (10**9 + 7) in each step to keep the results small.

Thanks man. First I started calculating the modulo before multiplying two numbers, but it still wouldn’t help. Then I tried the multiplicative inverse, and after a bit of research, it worked.