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)$
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$.
For each test case, print a line contained $n$ integers, the $i$th integer represents $g(i)$.