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 $f(i), 1 \le i \le n$, calculate
$\displaystyle g(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} \sum_{i_3 \mid i_2} \cdots \sum_{i_k \mid i_{k-1}} f(i_k) \text{ mod } 1000000007 \quad (1 \le i \le n)$
Input
The first line contains an integer $T(1 \le T \le 5)$, the number of test cases.
For each test case, the first line contains two integers $n, k(1 \le n, k \le 100000)$.
The second line contains $n$ integers, the $i$th integer denotes $f(i), 0 \le f(i) < 10^9+7$.
Output
For each test case, print a line contained $n$ integers, the $i$th integer represents $g(i)$.
In the first sample case:
f(1)=2,f(2)=f(3)=f(4)=f(5)=f(6)=3
when k=1
g(1)=f(1)=2,g(2)=f(1)+f(2)=5,g(3)=f(1)+f(3)=5,g(4)=f(1)+f(2)+f(4)=2+3+3=8,g(5)=f(1)+f(5)=5,g(6)=f(1)+f(2)+f(3)+f(6)=2+3+3+3=10
when k=2
g(1)=f(1)=2,g(2)=f(1)+(f(1)+f(2))=7,g(3)=f(1)+(f(1)+f(3))=7,g(4)=f(1)+(f(1)+f(2))+(f(1)+f(4))=15,g(5)=f(1)+(f(1)+f(5))=7,g(6)=f(1)+(f(1)+f(2))+(f(1)+f(3))+(f(1)+f(2)+f(3)+f(6))=23
Therefore output
2 7 7 15 7 23
