BTCODE_E  Recover Polynomials
Venkatesh is an expert in mathematics, and loves playing around with polynomials during his free time. His favourite mathematical equation is pretty obviously: f(x) = a_{n}*x^{n} + a_{n1}*x^{n1} + ..... + a_{1}*x + a_{0}. His friend Suhash loves posing challenges to Venkatesh. Once they were discussing a particular problem at Snacky, which goes as follows:
Suhash would choose an integer 'n' as the degree of the polynomial and give Venkatesh the value of the polynomial at 'n+1' equally spaced points, i.e he gives Venkatesh integers 'n', 'x_{0}', 'd' and g_{0}, g_{1}, g_{2}, ..., g_{n} such that: f(x_{0}) = g_{0}, f(x_{0}+d) = g_{1}, f(x_{0}+2*d) = g_{2}, ......f(x_{0}+n*d) = g_{n}. Now, Venkatesh is required to find the polynomial. Since he hates floating point values, he decides to find the polynomial in coefficient form, modulo a prime number. Can you help Venkatesh find the polynomial?
Input
The first line of input contains an integer 't', denoting the number of test cases.
For each test case, the first line contains 3 space separated integers 'n', 'x_{0}', 'd'. The next line contains 'n+1' space separated integers g_{0}, g_{1}, g_{2}, .....g_{n}.
Output
For each test case output 'n+1' integers, denoting the coefficients of the polynomial a_{0}, a_{1}, a_{2},...... a_{n}. All the coefficients that are printed should be nonnegative and should be less than 1000000007.
You are required to find coefficients of the polynomial a_{0}, a_{1}, a_{2},...... a_{n}, which satisfy the equations: f(x_{0})%1000000007 = g_{0}, f(x_{0}+d)%1000000007 = g_{1}, ....... f(x_{0}+n*d)%1000000007 = g_{n}. It is guarenteed that there is a unique solution for every test case.
Example
Input: 1 3 1 1 10 26 58 112 Output: 4 3 2 1 Constraints: t <= 25 1 <= n <= 1000 0 <= x_{0} <= 100000 0 < d <= 10000 0 <= g_{i} <= 10^9
Explanation:
Test case 1: It can be seen that the polynomial f(x) = x^{3} + 2*x^{2} + 3*x + 4 satisfies the above input.
hide comments
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20140102 04:40:28
Nevermind :P 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120809 17:04:02
Whaa.... GaussJordan elimination is TLE! Is there any faster algorithm than that? Tell me what is it? 
Added by:  suhash 
Date:  20110226 
Time limit:  2.090s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Bytecode 2011, NIT Trichy, India 