问题描述
克拉克是一名人格分裂患者。某一天他变成一名数学家，在研究奇怪的东西。
他突然想算这么一个式子，给出$f(i), 1 \le i \le n$，要求算
$\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)$
输入描述
第一行一个整数$T(1 \le T \le 5)$，表示数据组数。
每组数据第一行为两个整数$n, k(1 \le n, k \le 100000)$。
接下来一行$n$个整数，第$i$个整数代表$f(i), 0 \le f(i) < 10^9+7$。
输出描述
每组数据输出一行$n$个数，第$i$个表示$g(i)$。
输入样例
2
6 2
2 3 3 3 3 3
23 3
2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
输出样例
2 7 7 15 7 23
2 9 9 24 9 39 9 50 24 39 9 102 9 39 39 90 9 102 9 102 39 39 9
Hint
在第一组样例中
f(1)=2,f(2)=f(3)=f(4)=f(5)=f(6)=3
当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
当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
故输出
2 7 7 15 7 23
