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 1st 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. 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 => Day 1 Day 2 Day 3 At the end Initial Step 1 Step2 Step2 Initial Step 1 Step2 Step3 3 2 1 2 1 1 2 1 1 2+1+1 2 1 4 2+12 4 3 2 4 3 2 4+3+2 4 2 9 4+24 9 6 4 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.
2/2 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. Sample Input 3 37 123 22 45 21 1 10 Sample Output 129 189 277 59 1 10