### Problem Description:

Clarke is a patient with multiple personality disorder. One day, he turned into a mathematician, did a research on interesting things.
Suddenly he found a interesting formula. Given $1\le i\le n$ , calculate $g(i)=\sum_{i_1|i}\sum_{i_2|i_1}\sum_{i_3|i_2}\ldots \sum_{i_k|i_{k-1}} f(i_k) \pmod {1000000007} ,1\le i\le n$

### Input:

The first line contains an integer T(1≤T≤5), the number of test cases.
For each test case, the first line contains two integers n,k(1≤n,k≤100000).
The second line contains n integers, the ith integer denotes f(i),0≤f(i)<109+7.

### Output:

For each test case, print a line contained n integers, the ith integer represents g(i).