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ⁿ + a_n-1*x^n-1 + ... + a₁*x + a₀. 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₀', 'd' and g₀, g₁, g₂ ... g_n such that: f(x₀) = g₀, f(x₀+d) = g₁, f(x₀+2*d) = g₂... f(x₀+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₀', 'd'. The next line contains 'n+1' space separated integers g₀, g₁, g₂ ... g_n.

Output

For each test case output 'n+1' integers, denoting the coefficients of the polynomial a₀, a₁, a₂ ... 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₀, a₁, a₂ ... a_n, which satisfy the equations: f(x₀)%1000000007 = g₀, f(x₀+d)%1000000007 = g₁ ... f(x₀+n*d)%1000000007 = g_n. It is guaranteed that there is a unique solution for every test case.

Constraints

t <= 25
1 <= n <= 1000
0 <= x₀ <= 100000
0 < d <= 10000
0 <= g_i <= 10^9

Example

Input:
1
3 1 1
10 26 58 112

Output:
4 3 2 1

Explanation

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