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.