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.

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.