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;
int n, k, d[32000];
long long nCr[2005][4015], mult;
void binom(int x) {
  if (x > k - 1) {
    nCr[0][x] = 0;
    return;
  }
  int a = x;
  for (int p = 2; p * p <= a; ++p) {
    if (a % p == 0) {
      --d[p];
      a /= p;
      --p;
    }
  }
  --d[a];
  a = k - x;
  for (int p = 2; p * p <= a; ++p) {
    if (a % p == 0) {
      ++d[p];
      a /= p;
      --p;
    }
  }
  if (a >= 32000)
    mult = (mult * a) % 1000000007LL;
  else
    ++d[a];
  nCr[0][x] = mult;
  for (int i = 2; i < 32000; ++i)
    for (int j = 0; j < d[i]; ++j) nCr[0][x] = (nCr[0][x] * i) % 1000000007LL;
}
long long in[2005];
int main() {
  scanf("%d%d", &n, &k);
  if (!k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) nCr[i][j] = 0;
    }
    nCr[0][0] = 1;
  } else {
    mult = 1;
    nCr[0][0] = 1;
    for (int i = 1; i < 2 * n + 4; ++i) {
      binom(i);
    }
    for (int i = 0; i < n; ++i) {
      nCr[i + 1][0] = 1;
      for (int j = 0; j < 2 * n + 1 - i; ++j) {
        nCr[i + 1][j + 1] = (nCr[i][j] + nCr[i][j + 1]) % 1000000007LL;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    scanf("%I64d", in + i);
  }
  for (int i = 0; i < n; ++i) {
    long long k = 0;
    for (int j = 0; j <= i; ++j) {
      k = (k + in[j] * nCr[i - j][i - j]) % 1000000007LL;
    }
    printf("%I64d ", k);
  }
  return 0;
}
