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;
template <typename T>
inline T BigMod(T A, T B, T M = MOD) {
  T ret = 1;
  while (B) {
    if (B & 1) ret = (ret * A) % M;
    A = (A * A) % M;
    B = B >> 1;
  }
  return ret;
}
template <typename T>
inline T EGCD(T a, T b, T &x, T &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T x1, y1;
  T d = EGCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
template <typename T>
inline T LCM(T x, T y) {
  T g = __gcd(x, y);
  return (x / g) * y;
}
template <typename T>
inline T Distance(T x1, T y1, T x2, T y2) {
  return sqrt(((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2)));
}
template <typename T>
inline T Area(T Ax, T Ay, T Bx, T By, T Cx, T Cy) {
  T ret = Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By);
  if (ret < 0) return ret = -ret;
  return ret;
}
bool Check(int N, int pos) { return (bool)(N & (1 << pos)); }
int Set(int N, int pos) { return (N | (1 << pos)); }
template <typename T>
inline T CRT(T num[], T rem[], T k) {
  T prod = 1, result = 0;
  for (T i = 0; i < k; i++) prod *= num[i];
  for (T i = 0; i < k; i++) {
    T pp = prod / num[i];
    result += rem[i] * inv(pp, num[i]) * pp;
  }
  return result % prod;
}
const int FacN = 100000;
long long Fac[FacN + 5];
void Facgen() {
  Fac[0] = 1;
  for (int i = 1; i <= FacN; i++) Fac[i] = (Fac[i - 1] * i) % MOD;
}
template <typename T>
inline T COM(T a, T b) {
  if (a < b) return 0;
  long long u = 1, d = 1;
  for (long long i = a - b + 1; i <= a; i++) u = (u * i) % MOD;
  for (long long i = 2; i <= b; i++) d = (d * i) % MOD;
  return (u * BigMod(d, MOD - 2, MOD)) % MOD;
}
long long ara[2002];
long long val[2002];
long long pre[2002];
long long n, k;
int main() {
  Facgen();
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> ara[i];
  if (k == 0) {
    for (int i = 1; i <= n; i++) cout << ara[i] << ' ';
    return 0;
  }
  for (int i = 0; i <= 2001; i++) pre[i] = COM(i + k - 1, (long long)i);
  for (int i = 1; i <= n; i++) {
    for (long long j = i, d = 0; j <= n; j++, d++) {
      long long x = (pre[d] * ara[i]) % MOD;
      val[j] = (val[j] + x) % MOD;
    }
  }
  for (int i = 1; i <= n; i++) cout << val[i] << " ";
}
