Problem C - Colorful Eggs

Little Mou is very fond of eggs. She has n baskets for keeping her colorful eggs. Each basket contains eggs of different colors. The baskets are numbered from 1 to n. She has a strange hobby about these eggs. On each day, she takes each basket starting from the n^th basket. When she is doing this for basket i, she counts all eggs placed in baskets 1 to i (inclusive) and takes their sum. Let this value of sum be counti. She removes all old eggs from the ith basket and keeps counti new eggs in the i^th basket. After that she puts all the old eggs of the i^th basket in the (i-1)^th basket removing the old eggs of the (i-1)^th basket. As Mou is very fond of eggs, she eats all old eggs of the (i-1)^th basket. And when she has finished eating, she repeats the work for this (i-1)^th basket. If she reaches the 1^st basket, she stops her work and doesn't eat any more eggs and goes to sleep!

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

So simulation for day 3 follows:

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.

3
3 7
1 2 3
2 2
4 5
2 1
1 10

129 189 277
5 9
1 10