SP8423 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 $ _{n-1} $ \*x $ ^{n-1} $ + ..... + 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?

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} $ .

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 non-negative 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.