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>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
template <typename T>
inline bool remin(T& c, const T& n) {
  if (n < c) {
    c = n;
    return 1;
  }
  return 0;
}
template <typename T>
inline bool remin2(T& c, const T& n) {
  if (c < 0 || n < c) {
    c = n;
    return 1;
  }
  return 0;
}
template <typename T>
inline bool remax(T& c, const T& n) {
  if (c < n) {
    c = n;
    return 1;
  }
  return 0;
}
template <typename T>
inline void addmod(T& c, const T& n, const T& m) {
  c = (c + n) % m;
}
int _in;
int in() {
  scanf("%d", &_in);
  return _in;
}
const int N = 1e3 + 5, MOD = 1e9 + 7;
int maj[N], ans[N], n, k;
long long mult(long long a, long long b, const long long& mod) {
  int i;
  long long ans = 0;
  for ((i) = (0); (i) < (63); ++(i)) {
    if ((1LL << i) & a) {
      ans = (ans + b) % mod;
    }
    b = b * 2 % mod;
  }
  return ans;
}
long long bin(int n, int m) {
  int i;
  long long up = 1, down = 1, mod;
  for ((i) = (2); (i) <= (n - m); ++(i)) {
    down = down * i % MOD;
  }
  mod = down * MOD;
  for ((i) = (m + 1); (i) <= (n); ++(i)) {
    up = mult(up, i, mod);
  }
  return up / down;
}
long long b[N];
int main() {
  int i, j;
  scanf("%d%d", &n, &k);
  for ((i) = (0); (i) < (n); ++(i)) {
    scanf("%d", maj + i);
  }
  if (k == 0) {
    copy(maj, maj + n, ans);
  } else {
    for ((i) = (0); (i) < (n); ++(i)) {
      b[i] = bin(i + k - 1, k - 1);
    }
    memset(ans, 0, sizeof(ans));
    for ((i) = (0); (i) < (n); ++(i)) {
      for ((j) = (0); (j) <= (n - i); ++(j)) {
        ans[i + j] = (long long(ans[i + j]) + maj[i] * b[j]) % MOD;
      }
    }
  }
  for ((i) = (0); (i) < (n); ++(i)) {
    printf("%d ", ans[i]);
  }
  putchar('\n');
  return 0;
}
