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 int oo = 0x3f3f3f3f;
const double eps = 1e-9;
int n, k;
vector<vector<unsigned long long> > multiply(
    vector<vector<unsigned long long> > &a,
    vector<vector<unsigned long long> > &b) {
  vector<vector<unsigned long long> > ret(int((a).size()));
  for (int i = (0); i < (int((a).size())); i++) {
    ret[i].resize(int((b[0]).size()));
    for (int j = (i); j < (int((b[0]).size())); j++) {
      unsigned long long s = 0;
      for (int k = (0); k < (int((a[0]).size())); k++)
        s = (s + a[i][k] * b[k][j]) % 1000000007;
      ret[i][j] = s;
    }
  }
  return ret;
}
vector<vector<unsigned long long> > multiply2(
    vector<vector<unsigned long long> > &a,
    vector<vector<unsigned long long> > &b) {
  vector<vector<unsigned long long> > ret(int((a).size()));
  ret[0].resize(int((b[0]).size()));
  for (int j = (0); j < (int((b[0]).size())); j++) {
    unsigned long long s = 0;
    for (int k = (0); k < (j + 1); k++)
      s = (s + a[0][k] * b[0][j - k]) % 1000000007;
    ret[0][j] = s;
  }
  return ret;
}
vector<vector<unsigned long long> > fastExp(
    vector<vector<unsigned long long> > &a, int n) {
  if (n == 1) return a;
  if (n % 2) {
    vector<vector<unsigned long long> > tmp = fastExp(a, n - 1);
    return multiply2(a, tmp);
  }
  vector<vector<unsigned long long> > ret(fastExp(a, n / 2));
  return multiply2(ret, ret);
}
int main() {
  cin >> n >> k;
  vector<vector<unsigned long long> > tmp(n);
  for (int i = (0); i < (n); i++) {
    tmp[i].resize(n);
    for (int j = (i); j < (n); j++) tmp[i][j] = 1;
  }
  if (k != 0) tmp = fastExp(tmp, k);
  for (int i = (1); i < (n); i++)
    for (int j = (i); j < (n); j++) tmp[i][j] = tmp[0][j - i];
  vector<vector<unsigned long long> > in(1);
  in[0].resize(n);
  for (int i = (0); i < (n); i++) cin >> in[0][i];
  if (k != 0)
    tmp = multiply(in, tmp);
  else
    tmp = in;
  for (int i = (0); i < (n); i++) {
    if (i != 0) cout << " ";
    cout << tmp[0][i] % 1000000007;
  }
  cout << endl;
  return 0;
}
