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 double PI = acos(-1);
const double EPS = 1e-7;
const long long MOD = 1000000007;
const long long PHI = 1000000005;
const long long MAX_N = 2000;
struct Matrix {
  int _R, _C;
  vector<vector<long long> > _data;
  void init() {
    _data.resize(_R);
    for (int(i) = 0, (_batas) = (((int)(_data).size())); (i) < (_batas); (i)++)
      _data[i].resize(_C);
  }
  Matrix(int R, int C) : _R(R), _C(C) { init(); }
  Matrix(int R, int C, int x) : _R(R), _C(C) {
    assert(_R == _C);
    x %= MOD;
    init();
    for (int(i) = 0, (_batas) = (_R); (i) < (_batas); (i)++) _data[i][i] = x;
  }
  Matrix operator*(Matrix other) {
    assert(this->_C == other._R);
    Matrix ret(this->_R, other._C);
    for (int(i) = 0, (_batas) = (ret._R); (i) < (_batas); (i)++) {
      for (int(j) = 0, (_batas) = (ret._C); (j) < (_batas); (j)++) {
        long long sum = 0;
        for (int(k) = 0, (_batas) = (this->_C); (k) < (_batas); (k)++) {
          sum = (sum + (this->_data[i][k] * other._data[k][j]) % MOD) % MOD;
        }
        ret._data[i][j] = sum;
      }
    }
    return ret;
  }
  void fromVector(vector<long long> v) {
    assert(this->_R * this->_C == ((int)(v).size()));
    for (int(i) = 0, (_batas) = (this->_R); (i) < (_batas); (i)++)
      for (int(j) = 0, (_batas) = (this->_C); (j) < (_batas); (j)++)
        this->_data[i][j] = v[i * this->_C + j];
  }
  void print() {
    for (int(i) = 0, (_batas) = (this->_R); (i) < (_batas); (i)++) {
      for (int(j) = 0, (_batas) = (this->_C); (j) < (_batas); (j)++) {
        cout << this->_data[i][j] << " ";
      }
      cout << endl;
    }
    cout << "--" << endl;
  }
};
long long N, K;
long long data[MAX_N + 5];
void cetak() {
  for (int(i) = 0, (_batas) = (N); (i) < (_batas); (i)++) {
    cout << data[i];
    if (i < N - 1) cout << " ";
  }
  cout << endl;
}
long long bigmod(long long a, long long b, long long c) {
  if (b == 0) return 1;
  long long tmp = bigmod(a, b / 2, c);
  tmp = tmp * tmp % c;
  if (b % 2) tmp = tmp * a % c;
  return tmp;
}
int main() {
  cin >> N >> K;
  for (int(i) = 0, (_batas) = (N); (i) < (_batas); (i)++) cin >> data[i];
  if (K == 0) {
    cetak();
    exit(0);
  }
  long long currN = K - 1;
  long long currK = 0;
  long long currVal = 1;
  vector<long long> mat;
  for (int(i) = 0, (_batas) = (N); (i) < (_batas); (i)++) {
    mat.push_back(currVal);
    if (i < N - 1) {
      currVal =
          (((currVal * (currN + 1)) % MOD) * bigmod(currK + 1, PHI, MOD)) % MOD;
      currN++;
      currK++;
    }
  }
  Matrix awal(1, N);
  awal.fromVector(vector<long long>(data, data + N));
  Matrix pow(N, N);
  for (int(i) = 0, (_batas) = (N); (i) < (_batas); (i)++) {
    for (int(j) = 0, (_batas) = (N); (j) < (_batas); (j)++) {
      if (j - i >= 0)
        pow._data[i][j] = mat[j - i];
      else
        pow._data[i][j] = 0;
    }
  }
  Matrix ret = awal * pow;
  for (int(i) = 0, (_batas) = (N); (i) < (_batas); (i)++) {
    cout << ret._data[0][i];
    if (i < N - 1) cout << " ";
  }
  cout << endl;
  return 0;
}
