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 chh;
const int N = 2000, MOD = 1000000007;
int n, k;
int a[N];
inline void in(int &t) {
  int n = 0, s = 1;
  char ch = getchar();
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') s = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') n = n * 10 + ch - '0', ch = getchar();
  t = n * s;
}
long long power(long long a, long long b, long long n) {
  long long res = 1;
  for (; b; b >>= 1, a = a * a % n)
    if (b & 1) res = res * a % n;
  return res;
}
long long cal(long long n, long long r, long long p) {
  long long i, res = 1, re;
  for (i = 1; i <= r; i++) {
    res = res * (n - i + 1) % p;
    re = power(i, p - 2, p);
    res = res * re % p;
  }
  return res;
}
long long lucas(long long n, long long m, long long p) {
  if (n < m)
    return 0;
  else
    return cal(n, m, p);
}
int val[N], ans[N];
int main() {
  int i, j, t;
  long long tmp, tt;
  in(n), in(k);
  for (i = 0; i < n; i++) in(val[i]);
  for (i = 0; i < n; i++) a[i] = (int)cal(k - 1 + i, i, MOD);
  for (i = 0; i < n; i++) {
    ans[i] = 0;
    for (j = i; j >= 0; j--) {
      ans[i] = ((long long)ans[i] + (long long)a[i - j] * val[j]) % MOD;
    }
  }
  for (i = 0; i < n - 1; i++) printf("%d ", ans[i]);
  printf("%d\n", ans[n - 1]);
  return 0;
}
