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 long long mod = 1e9 + 7;
const long long G = 3;
const long long maxn = 3000001;
long long read() {
  long long s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}
inline long long read2() {
  long long x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = (1ll * x * 10 + ch - '0'), ch = getchar();
  return x;
}
inline void print(long long *f, long long len) {
  for (long long i = 0; i < len; i++) printf("%lld ", f[i]);
  puts("");
}
long long n, m, k, opt;
long long qpow(long long a, long long b = mod - 2) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ans;
}
const long long invG = qpow(G);
long long tr[maxn], f[maxn], g[maxn], invn, trs;
void poly_pre(long long n) {
  if (trs == n) return;
  trs = n;
  for (long long i = 0; i < n; ++i)
    tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
}
void ntt(long long *f, long long n, bool op) {
  poly_pre(n);
  for (long long i = 0; i < n; ++i) {
    if (i < tr[i]) swap(f[i], f[tr[i]]);
  }
  for (long long p = 2; p <= n; p <<= 1) {
    long long len = (p >> 1);
    long long bas = qpow(op == 1 ? G : invG, (mod - 1) / p);
    for (long long k = 0; k < n; k += p) {
      long long buf = 1;
      for (long long l = k; l < k + len; ++l) {
        long long kk = buf * f[l + len] % mod;
        f[l + len] = f[l] - kk;
        if (f[len + l] < 0) f[len + l] += mod;
        f[l] = f[l] + kk;
        f[l] %= mod;
        buf *= bas, buf %= mod;
      }
    }
  }
  if (!op) {
    long long invn = qpow(n);
    for (long long i = 0; i < n; ++i) f[i] = (f[i] * invn) % mod;
  }
}
long long ze[10101];
void poly_mul(long long *f, long long *g, long long n) {
  for (long long i = 0; i < n; ++i) f[i] = f[i] * g[i] % mod;
}
long long inv[maxn];
signed main() {
  inv[1] = 1;
  for (long long i = 2; i <= 600000; i++)
    inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
  long long T = 1;
  while (T--) {
    n = read(), k = read2();
    opt = 0;
    for (long long i = 0; i < n; ++i) f[i] = read();
    m = n;
    g[0] = 1;
    if (opt) {
      for (long long i = 1; i < m; ++i) {
        g[i] = 1LL * g[i - 1] * (k - i + 1 + mod) % mod * inv[i] % mod;
      }
      for (long long i = 1; i < m; i += 2) g[i] = mod - g[i];
    } else {
      for (long long i = 1; i < m; ++i) {
        g[i] = 1LL * g[i - 1] * (i + k - 1) % mod * inv[i] % mod;
      }
    }
    for (long long i = 0, iend = m - 1; i <= iend; ++i)
      for (long long j = 0, jend = m - 1; j <= jend; ++j)
        ze[i + j] += f[i] * g[j] % mod, ze[i + j] %= mod;
    print(ze, m);
  }
}
