CF223C.Partial Sums

You've got an array a, consisting of n integers. The array elements are indexed from 1 to n. Let's determine a two step operation like that:

1. First we build by the array a an array s of partial sums, consisting of n elements. Element number i (1 ≤ i ≤ n) of array s equals . The operation x mod y means that we take the remainder of the division of number x by number y.
2. Then we write the contents of the array s to the array a. Element number i (1 ≤ i ≤ n) of the array s becomes the i-th element of the array a (a__i = s__i).

You task is to find array a after exactly k described operations are applied.

你有一个包含 $ n $ 个整数的数组 $ a $。数组元素的下标从 $ 1 $ 到 $ n $。我们定义如下两步操作：

1. 首先，根据数组 $ a $ 构造一个由 $ n $ 个元素组成的前缀和数组 $ s $。数组 $ s $ 的第 $ i $ 个元素（$ 1 \leq i \leq n $）等于
   。
   运算 $ x \bmod y $ 表示 $ x $ 除以 $ y $ 所得的余数。
2. 然后，将数组 $ s $ 的内容写回数组 $ a $：即数组 $ s $ 的第 $ i $ 个元素成为数组 $ a $ 的第 $ i $ 个元素（$ a_i = s_i $）。

你的任务是：求对数组 $ a $ 恰好执行 $ k $ 次上述操作后得到的数组 $ a $。

The first line contains two space-separated integers n and k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 109). The next line contains n space-separated integers _a_1, _a_2, ..., a__n — elements of the array a (0 ≤ a__i ≤ 109).

第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 2000$，$0 \leq k \leq 10^9$）。
下一行包含 $n$ 个以空格分隔的整数 $a_1,\,a_2,\,\dots,\,a_n$ —— 数组 $a$ 的元素（$0 \leq a_i \leq 10^9$）。

Print n integers — elements of the array a after the operations are applied to it. Print the elements in the order of increasing of their indexes in the array a. Separate the printed numbers by spaces.

输出对数组 $a$ 执行所有操作后得到的 $n$ 个整数——即数组 $a$ 的元素。按这些元素在数组 $a$ 中下标递增的顺序输出。各输出数字之间用空格分隔。