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).

Sample Input:


Sample Output:


题解:


这个题目有两个做法。
我们可以考虑 \(f(j)\)\(g(i)\) 的贡献。
发现 \(g(i)=\sum_{j|i} H(\frac{i}{j}) f(j)\) ,其中 \(H(i)\) 表示把 \(i\) 分成 \(k\) 个有序数的乘积的方案数。
然后我们发现 \(H(i)\) 是积性的,还有 \(H(p^r)=\binom{k+r-1}{r}\) ,可以线性筛。
最后对于每一个 \(f(j)\) 枚举 \(j\) 的倍数 \(k\) ,对 \(g(k\times j)\) 产生贡献。
时间复杂度 \(O(n\ln n)\)

其实这个题目还是狄利克雷卷积的模板题。(虽然我之前并不知道这东西)
两个函数 \(f\)\(g\) 的狄利克雷卷积定义为 \((f \otimes g)(n) = \sum_{j|n} f(j) g(\frac{n}{j})\)
可以改写为 \((f\otimes g)(n) = \sum_{i\times j = n} f(j) g(i)\)
然后可以发现原式的一层就是一次 \(f\) 函数和 \(1\) 函数狄利克雷卷积。
因为狄利克雷卷积满足结合律,所以 \(g = f \otimes 1^k\) (其中1函数满足 \(1(x)=1\)
然后快速幂套一个狄利克雷卷积就可以了。
时间复杂度 \(O(n\log k \ln n)\)
稍微慢一些,但写起来方便一些。