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;
template <class T>
using vec = std::vector<T>;
bool __hack = std::ios::sync_with_stdio(false);
auto __hack1 = cin.tie(nullptr);
namespace template_util {
constexpr int bytecount(uint64_t x) { return x ? 1 + bytecount(x >> 8) : 0; }
template <int N>
struct bytetype {};
template <uint64_t N>
struct minimal_uint : bytetype<bytecount(N)> {};
}  // namespace template_util
template <class T>
T next(istream& in) {
  T ret;
  in >> ret;
  return ret;
}
template <class T>
vector<T> next_vec(istream& in, size_t n) {
  vector<T> ret(n);
  for (size_t i = 0; i < n; ++i) {
    ret[i] = next<T>(in);
  }
  return ret;
}
template <class T>
void outVec(ostream& out, const vector<T>& v) {
  out << v[0];
  for (size_t i = 1; i < v.size(); ++i) {
    out << ' ' << v[i];
  }
  out << "\n";
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T>
static constexpr T inverse2(T a, T m) {
  return a <= 1 ? a : mod((1 - inverse2(m % a, a) * m) / a, m);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return inverse2(mod(a, m), m);
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  static constexpr T reduce(T value, tag_plus) {
    return value >= Modulus ? value - Modulus : value;
  }
  static constexpr T reduce(T value, tag_minus) {
    return value < 0 ? value + Modulus : value;
  }
  static constexpr T reduce(T value, tag_good) { return value; }

 public:
  T value;
  constexpr MR() : value(0) {}
  constexpr MR(C value) : value(reduce(value % Modulus, tag_minus())) {}
  template <typename tag_t>
  constexpr MR(T value, tag_t tag) : value(reduce(value, tag)) {}
  MR& operator=(C value) {
    this->value = reduce(value % Modulus, tag_minus());
    return *this;
  }
  constexpr MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  constexpr MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  constexpr T get() const { return value; }
  constexpr MR inverse() const {
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  constexpr MR operator/(MR b) const { return *this * b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream& operator<<(std::ostream& o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
template <class T>
vector<T> getFactorials(int n) {
  vector<T> res(n);
  res[0] = T(1);
  for (int i = 1; i < n; ++i) {
    res[i] = res[i - 1] * i;
  }
  return res;
}
void solve(istream& in, ostream& out) {
  auto n = next<int>(in);
  auto k = next<int>(in);
  auto a = next_vec<int>(in, n);
  if (k == 0) {
    outVec(out, a);
    return;
  }
  vec<MR<int, int64_t, 1000000007> > f =
      getFactorials<MR<int, int64_t, 1000000007> >(n + 1);
  vec<MR<int, int64_t, 1000000007> > ki(n + 1);
  --k;
  ki[1] = MR<int, int64_t, 1000000007>(k + 1);
  for (int i = 2; i <= n; ++i) {
    ki[i] = ki[i - 1] * MR<int, int64_t, 1000000007>(k + i);
  }
  auto C2 = [&](int i) -> MR<int, int64_t, 1000000007> { return ki[i] / f[i]; };
  vec<MR<int, int64_t, 1000000007> > cRow(n);
  cRow[0] = 1;
  for (int i = 1; i < n; ++i) {
    cRow[i] = C2(i);
  }
  reverse(cRow.begin(), cRow.end());
  ;
  ;
  vec<MR<int, int64_t, 1000000007> > res;
  for (int i = 0; i < (n); ++i) {
    MR<int, int64_t, 1000000007> cur = 0;
    for (int j = 0; j < (n); ++j) {
      cur = cur + MR<int, int64_t, 1000000007>(a[j]) * cRow[j];
    }
    res.push_back(cur);
    cRow.push_back(0);
    cRow.erase(cRow.begin());
  }
  reverse(res.begin(), res.end());
  for (auto i : res) {
    out << i << ' ';
  }
  out << "\n";
}
int main() {
  solve(cin, cout);
  return 0;
}
