\(Description\)

　　$$g(i)=\sum_{i_1|i}\sum_{i_2|i_1}\sum_{i_3|i_2}\cdots\sum_{i_k|i_{k-1}}f(i_k)\ mod\ 1000000007$$

　　给出\(n,k,f[1\sim n]\)，求\(g[1\sim n]\).

\(Solution\)

　　首先狄利克雷卷积(Dirichlet Product)：设\(f(n),g(n)\)是两个数论函数，它们的Dirichlet乘积也是一个数论函数，

　　简记为\(h(n)=f(n)*g(n)\)。

狄利克雷卷积有几个性质：

　　1. 满足交换律 \(f*g=g*f\)

　　2. 满足结合律 \((f*g)*h=f*(g*h)\)

　　3. 满足分配率 \(f*(g+h)=f*g+f*h\)

　　4. 存在单位元\(e\)，使得\(e*f=f*e=f\)

　　回到本题。设\(I(x)=1\).

　　将式子依次展开

　　$$f'(i_{k-1})=\sum_{i_k|i_{k-1}}f(i_k)=\sum_{i_k|i_{k-1}}f(i_k)I(\frac{i_{k-1}}{i_k})\ ,\ \ 即f'=fI$$

　　$$f''(i_{k-2})=\sum_{i_{k-1}|i_{k-2}}f'(i_k-1)=\sum_{i_{k-1}|i_{k-2}}f'(i_k-1)I(\frac{i_{k-2}}{i_{k-1}})\ ,\ \ 即f''=f'*I$$.

　　\(\ldots\)

　　这样下去可以得到\(g=I*I*I*\cdots*I*f(k个I)\)。由于狄利克雷卷积满足结合律，所以\(k个I\)的狄利克雷卷积可以用快速幂\(logk\)计算。

　　计算狄利克雷卷积时，如果对每个\(g(i),1\leq i\leq n\)都按照定义枚举其约数计算，时间肯定爆炸。所以可以枚举约数，再枚举这些约数可以对哪些值给出贡献，那么计算一次狄利克雷卷积的复杂度就是\(O(nlogn)\)，总复杂度\(O(nlognlogk)\)。

/*

刚开始要将ans初始化为单位元，即ans[2~n]=0,ans[1]=1,这样最初乘一个函数还是这个函数本身，即1

初始化x为I,I(n)=1

注:1.两个函数狄利克雷卷积是个函数

2.加两个数取模不能直接用-=mod

*/

#include<cstdio>

#include<cctype>

#include<cstring>

#define gc() getchar()

typedef long long LL;

const int N=1e5+5,mod=1e9+7;

int n,k;

LL f[N],ans[N],tmp[N],x[N];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

#define Mod(x) x>=mod?x-=mod:0

void Dirichlet(LL *a,LL *b)//a*b

{

	memset(tmp,0,sizeof tmp);

	for(int i=1;i*i<=n;++i)

	{

		tmp[i*i]+=a[i]*b[i]%mod, Mod(tmp[i*i]);

		for(int j=i+1;i*j<=n;++j)//下边加上a[i]*b[j]和a[j]*b[i]，所以j从i+1开始即可

			(tmp[i*j]+=a[i]*b[j]%mod+a[j]*b[i]%mod)%=mod;//注意这加两个数不能一步用Mod取模。。

	}

	memcpy(a,tmp,sizeof tmp);

}

void Solve()

{

	for(int i=1;i<=n;++i) x[i]=1,ans[i]=0;//x:I^0

	ans[1]=1;//ans:e

	for(;k;k>>=1,Dirichlet(x,x))

		if(k&1) Dirichlet(ans,x);

	Dirichlet(ans,f);

	for(int i=1;i<=n;++i) printf("%lld%c",ans[i],i==n?'\n':' ');//空格及换行符有要求

}

int main()

{

	for(int t=read();t--;)

	{

		n=read(),k=read();

		for(int i=1;i<=n;++i) f[i]=read();

		Solve();

	}

	return 0;

}