## BTCODE_E - Recover Polynomials

no tags

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) = an*xn + an-1*xn-1 + ..... + a1*x + a0. 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', 'x0', 'd' and g0, g1, g2, ..., gn such that: f(x0) = g0, f(x0+d) = g1, f(x0+2*d) = g2, ......f(x0+n*d) = gn. 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', 'x0', 'd'. The next line contains 'n+1' space separated integers g0, g1, g2, .....gn.

### Output

For each test case output 'n+1' integers, denoting the coefficients of the polynomial a0, a1, a2,...... an. 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 a0, a1, a2,...... an, which satisfy the equations: f(x0)%1000000007 = g0, f(x0+d)%1000000007 = g1, ....... f(x0+n*d)%1000000007 = gn. 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 <= x0 <= 100000
0 < d  <= 10000
0 <= gi <= 10^9

```

Explanation:

Test case 1: It can be seen that the polynomial f(x) = x3 + 2*x2 + 3*x + 4 satisfies the above input.