← 返回题目列表

Codeforces · 223/C

C. 部分和

中文机器翻译题面 查看原题

你有一个数组 a,由 n 个整数组成。数组元素的索引从 1 到 n。让我们确定这样的两步操作:

1. 首先,我们通过数组 a 构建一个由 n 个元素组成的部分和数组 s。数组 s 的元素编号 i (1 ≤ i ≤ n) 等于 $$s_i = \left( \sum_{j=1}^{i} a_j \right) \mod (10^9 + 7)$$。 x mod y 运算表示我们取数字 x 除以数字 y 的余数。
2.然后我们将数组s的内容写入数组a。数组s的元素编号i(1 ≤ i ≤ n)成为数组a的第i个元素(ai = si)。

您的任务是在应用了 k 个所描述的操作后找到数组 a。

输入

第一行包含两个空格分隔的整数 n 和 k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 109)。下一行包含 n 个空格分隔的整数 a1, a2, ..., an — 数组 a 的元素 (0 ≤ ai ≤ 109)。

输出

打印 n 个整数 — 应用运算后数组 a 的元素。按照数组 a 中索引递增的顺序打印元素。用空格分隔打印的数字。

示例

输入 #1

3 1
1 2 3

输出 #1

1 3 6

输入 #2

5 0
3 14 15 92 6

输出 #2

3 14 15 92 6