UVa 12042 - Colorful Eggs

Problem

For example let Mou has 3 baskets at day 1. 1st basket contains 1 egg, 2nd basket contains 1 egg and the 3rd basket contains 2 eggs.

So simulation for day 3 follows:

Basket Index => 3 2 1

….. 略

Now the problem is given n, d and the number of eggs in each basket eggi, your job is to find the number of eggs in each basket after d days. As the number can be very big output answer modulo 1,000,000,007.

Input

The first line of the input file contains an integer T (T ≤ 111) which denotes the total number of test cases. The description of each test case is given below:

Two integers N (1 ≤ n ≤ 60) and d (1 ≤ d ≤ 1,000,000,000), followed by n integers denoting the number of eggs in each basket starting from 1 to n.
Output

For each test case print one line of output containing the number of eggs in each basket after d days have passed separated by single spaces between them. See the sample output for more details. As the numbers can be very big output answer modulo 1,000,000,007.