奇怪的事情发生了！星际猫开始学前缀和了！ 猫猫刚刚学习了前缀和的思想，他觉得前缀和实在是太奇妙啦。于是在闲暇时间里，他拿出一个长度为 $n$ 的数字序列，开始对其进行“前缀和变换”。 对于一个包含 $n$ 个数字的序列 $\{a_1,a_2,a_3,\cdots,a_n\}$ ，进行一次“前缀和变换”后，其第 $p$ 个位置的元素值将会从 $a_p$ 变为 $a_1+a_2+\cdots+a_p$ ，因此这个序列会变为 $\{a_1,a_1+a_2,a_1+a_2+a_3,\cdots,a_1+a_2+\cdots+a_n\}$ 。 猫猫想知道进行 $m$ 次变换后，序列的结果如何。 但变换次数太多了，猫猫又不会数数，所以请你帮助猫猫吧，喵喵喵o(=•ェ•=)o

第一行包含两个正整数 $n,m\ (1\le n\le 8888,1\le m\le 10^6)$ 。 第二行包含 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n\ (0\le a_i\le 10)$ ，表示初始序列。

在一行内输出 $n$ 个整数，表示进行 $m$ 次变换后序列每个位置的元素值。 答案可能很大，输出对 $10^9+7$ 取模后的结果即可。

*对于样例一* 序列 $1,1,1,1$ 每次变换后的结果为： $1,2,3,4$ $1,3,6,10$ $1,4,10,20$ $1,5,15,35$ $1,6,21,56$