Hints: The testing suite has low memory, if you're getting no answers or weird aborts in the testing suite, it's probably a memory overflow.

Hint 2...

You don't need to solve any linear equations for this. I started down that path with implementing matrix functions...it's all unnecessary. I didn't even use binomial coefficients. You can get by with just the coefficients you start with.. My final python solution is only 15 lines. I don't even use pow.

The way the test cases are provided for this problem is really weird.

I made a mistake but my code could only go wrong with one specific input value. However I could pass no test cases other than #0.

It misled me into thinking that my algorithm was wrong.

When I modified my code to handle this special case, I jumped from 0% to 100%. So this special value is included in all test cases aside from the sample.

Obviously, better distribution is possible.

Optimum polynomial is a projected place, Where it is important to always mention all what we demand at most because mostly our demand need xpertwriters.com changes because it is not good at most of the place which they project all time.

It's getting very messy to deal with system of linear equations and polynomials without using numpy and sympy.

EDIT: It comes to me as a bit of surprise, that even with the beautiful use of binomial coefficients, the result is all TLE except the first test case. And when I look closely, it seems that it takes more than 6 seconds to calculate the original sequence terms with the polynomial coefficients provided.

Interestingly, when I suspect that the input A are too large to be multiplied and add the modulo to it before calculation, now it takes more than 7 seconds to get those terms. It couldn't be the problem with map(int, raw_input().split()), could it?

EDIT 2: One thing that caught my attention is the use of that makes it much faster than other choices when used as the modulo parameter in pow(). It seems to be a difference of few seconds, in this case. By the way, it's still meaningless as I should not use such a modulo in the intermediate steps. To really get this problem through I believe it is not required to get the original terms in the first place.

Just in case it mights help someone : 1.all these are binomial coefficients. 2.for the god of pythons, dont do (-1)**3000 (-_-)