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>
namespace IO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf, obuf[1 << 21], *p = obuf;
struct outflush {
  ~outflush() {
    (void)(fwrite(::IO::obuf, 1, ::IO::p - ::IO::obuf, stdout), fflush(stdout),
           ::IO::p = ::IO::obuf);
  }
} flushout;
}  // namespace IO
int rec() {
  int ch;
  while (isspace(ch = (::IO::p1 == ::IO::p2 &&
                               (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                           fread(::IO::ibuf, 1, 1 << 21, stdin),
                                ::IO::p1 == ::IO::p2)
                           ? EOF
                           : *::IO::p1++)))
    ;
  return ch;
}
bool rei(char& c) {
  int ch;
  while (isspace(ch = (::IO::p1 == ::IO::p2 &&
                               (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                           fread(::IO::ibuf, 1, 1 << 21, stdin),
                                ::IO::p1 == ::IO::p2)
                           ? EOF
                           : *::IO::p1++)))
    ;
  if (ch == EOF) return false;
  c = ch;
  return true;
}
bool rei(char* s) {
  if (!rei(*s)) return false;
  int ch;
  while (*++s = ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++),
         ch != EOF && !isspace(ch))
    ;
  *s = 0;
  return true;
}
template <class T>
bool rei(T& x) {
  bool f = true;
  int ch;
  for (ch = (::IO::p1 == ::IO::p2 &&
                     (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                 fread(::IO::ibuf, 1, 1 << 21, stdin),
                     ::IO::p1 == ::IO::p2)
                 ? EOF
                 : *::IO::p1++);
       !isdigit(ch);
       ch = (::IO::p1 == ::IO::p2 &&
                     (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                 fread(::IO::ibuf, 1, 1 << 21, stdin),
                     ::IO::p1 == ::IO::p2)
                 ? EOF
                 : *::IO::p1++)) {
    if (ch == EOF) return false;
    f = ch != '-';
  }
  x = 0;
  if (f) do
      x = x * 10 + (ch & 15);
    while (
        isdigit(ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++)));
  else
    do x = x * 10 - (ch & 15);
    while (
        isdigit(ch = (::IO::p1 == ::IO::p2 &&
                              (::IO::p2 = (::IO::p1 = ::IO::ibuf) +
                                          fread(::IO::ibuf, 1, 1 << 21, stdin),
                               ::IO::p1 == ::IO::p2)
                          ? EOF
                          : *::IO::p1++)));
  return true;
}
void pti(const char& c) {
  (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
       (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
   *::IO::p++ = c);
}
void pti(const char* s) {
  while (*s)
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = *s++);
}
template <class T>
void pti(T x) {
  char buf[sizeof(T) * 3], *p = buf + 1;
  if (x >= 0)
    *buf = (x % 10) | 48, x /= 10;
  else
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = '-'),
        *buf = (-(x % 10)) | 48, x = -(x / 10);
  while (x) *p++ = (x % 10) | 48, x /= 10;
  while (p != buf)
    (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
         (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
     *::IO::p++ = *--p);
}
template <class T>
void pri(const T& x) {
  pti(x), (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
               (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
           *::IO::p++ = ' ');
}
template <class T>
void prn(const T& x) {
  pti(x), (::IO::p == ::IO::obuf + sizeof(::IO::obuf) &&
               (fwrite(::IO::obuf, 1, 1 << 21, stdout), ::IO::p = ::IO::obuf),
           *::IO::p++ = '\n');
}
template <class T, class... Args>
bool rei(T&& x, Args&&... args) {
  return rei(std::forward<T>(x)) ? rei(args...) : false;
}
template <class T, class... Args>
void pti(const T& x, const Args&... args) {
  pti(x), pti(args...);
}
template <class T, class... Args>
void pri(const T& x, const Args&... args) {
  pri(x), pri(args...);
}
template <class T, class... Args>
void prn(const T& x, const Args&... args) {
  pri(x), prn(args...);
}
template <class T1, class T2>
T1& cmax(T1& a, const T2& b) {
  return a < b ? a = b : a;
}
template <class T1, class T2>
T1& cmin(T1& a, const T2& b) {
  return a > b ? a = b : a;
}
template <class T>
T lowbit(const T& x) {
  return x & -x;
}
using namespace std;
const long long MAXN = 2005;
long long inv[MAXN], t[MAXN];
long long n, k;
long long a[MAXN];
signed main() {
  rei(n, k);
  for (long long i = 1, i_end = n; i <= i_end; ++i) {
    rei(a[i]);
  }
  inv[1] = 1;
  for (long long i = 2, i_end = n; i <= i_end; ++i) {
    inv[i] = inv[1000000007 % i] * (1000000007 - 1000000007 / i) % 1000000007;
  }
  t[0] = 1;
  for (long long i = 1, i_end = n; i <= i_end; ++i) {
    t[i] = t[i - 1] * (i + k - 1) % 1000000007 * inv[i] % 1000000007;
  }
  for (long long i = 1, i_end = n, ans; i <= i_end; ++i) {
    ans = 0;
    for (long long j = 1, j_end = i; j <= j_end; ++j) {
      (ans += t[i - j] * a[j] % 1000000007) %= 1000000007;
    }
    pri(ans);
  }
  return 0;
}
