No tag edit access

C. Partial Sums

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou'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:

- 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*. - 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.

Input

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}).

Output

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.

Examples

Input

3 1

1 2 3

Output

1 3 6

Input

5 0

3 14 15 92 6

Output

3 14 15 92 6

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2017 12:10:33 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|