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>
#pragma comment(linker, "/STACK:102400000,102400000")
using std::bitset;
using namespace std;
long long f[2100];
long long n, k;
long long jie[2100], re[2100];
long long a[2100], ans[2100];
void e_gcd(long long a, long long b, long long &x, long long &y) {
  long long i, j, tem;
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  e_gcd(b, a % b, x, y);
  tem = x;
  x = y;
  y = tem - a / b * y;
}
long long C(long long n, long long k) {
  long long i, j, tem;
  long long sum = 1;
  for (i = n; i >= n - k + 1; i--) sum = (sum * i) % 1000000007;
  sum = (sum * re[k]) % 1000000007;
  return sum;
}
void cau() {
  long long i, j, tem;
  if (k == 0) {
    memset(f, 0, sizeof(f));
    ;
    f[1] = 1;
    return;
  }
  if (k == 1) {
    for (i = 1; i <= n; i++) f[i] = 1;
    return;
  }
  f[1] = 1;
  for (i = 2; i <= n; i++) f[i] = C(k + i - 2, i - 1);
}
void init() {
  long long i, j, tem, x, y;
  jie[0] = 1;
  for (i = 1; i <= 2000; i++) {
    jie[i] = (i * jie[i - 1]) % 1000000007;
    e_gcd(jie[i], 1000000007, x, y);
    re[i] = (x + 1000000007) % 1000000007;
  }
}
int main() {
  long long i, j, tem;
  init();
  while (scanf("%I64d%I64d", &n, &k) != EOF) {
    for (i = 1; i <= n; i++) scanf("%I64d", &a[i]);
    cau();
    memset(ans, 0, sizeof(ans));
    ;
    for (i = 1; i <= n; i++) {
      for (j = i; j > 0; j--)
        ans[i] = (ans[i] + a[i - j + 1] * f[j] % 1000000007) % 1000000007;
    }
    for (i = 1; i < n; i++) printf("%I64d ", ans[i]);
    printf("%I64d\n", ans[n]);
  }
  return 0;
}
