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 sz = 2010;
const long long mod = (long long)1e9 + 7;
long long _pow(long long a, long long n) {
  if (n == 0) return 1ll;
  a %= mod;
  long long tmp = _pow(a, n / 2);
  tmp = (tmp * tmp) % mod;
  if (n % 2 == 1ll) tmp = (a * tmp) % mod;
  while (tmp < 0) tmp += mod;
  return tmp;
}
long long inv(long long n) { return _pow(n, mod - 2); }
long long dp[sz];
long long readInt() {
  char ch;
  while ((ch = getchar()) < '0' || ch > '9')
    ;
  long long ret = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') ret = ret * 10 + ch - '0';
  return ret;
}
int main() {
  (mod);
  int N;
  long long K;
  long long a[sz];
  N = readInt();
  K = readInt();
  dp[0] = 1;
  for (int j = 1, lets_stop_here = (int)sz - 5; j <= lets_stop_here; j++) {
    dp[j] = (dp[j - 1] * (j + K - 1)) % mod;
    while (dp[j] < 0) dp[j] += mod;
    dp[j] = (dp[j] * inv(j)) % mod;
    while (dp[j] < 0) dp[j] += mod;
  }
  for (int i = 0, lets_stop_here = (int)N; i < lets_stop_here; i++)
    a[i] = readInt();
  char ans[2000 * 13] = {0};
  char *ptr = ans;
  for (int i = 0, lets_stop_here = (int)N; i < lets_stop_here; i++) {
    long long cur = 0;
    int k = 0;
    for (int k = 0, lets_stop_here = (int)i + 1; k < lets_stop_here; k++) {
      cur += (dp[k] * a[i - k]) % mod;
      cur %= mod;
    }
    ptr += sprintf(ptr, "%d ", (int)cur);
  }
  cout << ans;
  cout << ("\n");
  return 0;
}
