301194: CF223C. Partial Sums

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Partial Sums

题意翻译

给一个数组$a[]$, 定义一次操作为: 1. $$s_i = \left(\sum_{j=1}^{i}a_j \right) \bmod ({10}^9 + 7)$$ 2. $$a_i := s_i$$ 求$k$次操作后,数组中每个$a_i$的值。 $n \le 2000, k \le 10^9.$

题目描述

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF223C/c051478f9fc3965030766767424a5562a646a777.png). 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.

输入输出格式

输入格式


The first line contains two space-separated integers $ n $ and $ k $ ( $ 1<=n<=2000 $ , $ 0<=k<=10^{9} $ ). The next line contains $ n $ space-separated integers $ a_{1},a_{2},...,a_{n} $ — elements of the array $ a $ ( $ 0<=a_{i}<=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.

输入输出样例

输入样例 #1

3 1
1 2 3

输出样例 #1

1 3 6

输入样例 #2

5 0
3 14 15 92 6

输出样例 #2

3 14 15 92 6

Input

题意翻译

给一个数组$a[]$, 定义一次操作为: 1. $$s_i = \left(\sum_{j=1}^{i}a_j \right) \bmod ({10}^9 + 7)$$ 2. $$a_i := s_i$$ 求$k$次操作后,数组中每个$a_i$的值。 $n \le 2000, k \le 10^9.$

加入题单

上一题 下一题 算法标签: