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 <image>. 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 (ai = si). 



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 ≤ 109). The next line contains n space-separated integers a1, a2, ..., an — elements of the array a (0 ≤ ai ≤ 109).

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 11;
const int Mod = 1e9 + 7;
void at(long long& a) { a %= Mod; }
struct Matrix {
  int n;
  long long arr[N];
  void clear() {
    n = 0;
    memset(arr, 0, sizeof(arr));
  }
  friend Matrix operator*(const Matrix& a, const Matrix& b) {
    assert(a.n == b.n);
    Matrix tmp;
    tmp.clear();
    tmp.n = a.n;
    for (int i = 0; i < tmp.n; ++i)
      for (int j = 0, k = i; j <= i; ++j, --k) {
        tmp.arr[i] += a.arr[j] * b.arr[k];
        at(tmp.arr[i]);
      }
    return tmp;
  }
  void print() {
    for (int i = 0; i < n - 1; ++i) {
      printf("%lld ", arr[i]);
    }
    printf("%lld\n", arr[n - 1]);
  }
};
Matrix tmp, ans, all;
int n, k;
void init() {
  tmp.n = n;
  for (int i = 0; i < tmp.n; ++i) tmp.arr[i] = 1;
  ans.clear();
  ans.n = n;
  ans.arr[0] = 1;
  all.clear();
  all.n = n;
  for (int i = 0; i < n; ++i) {
    scanf("%lld", &all.arr[i]);
  }
}
void solve() {
  while (k) {
    if (k & 1) ans = ans * tmp;
    tmp = tmp * tmp;
    k >>= 1;
  }
  ans = ans * all;
  ans.print();
}
int main() {
  while (scanf("%d%d", &n, &k) == 2) {
    init();
    solve();
  }
}
