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 Max(int a, int b) { return (((b - a) >> (32 - 1)) & (a ^ b)) ^ b; }
int Min(int a, int b) { return (((b - a) >> (32 - 1)) & (a ^ b)) ^ a; }
long long GCD(long long a, long long b) { return b != 0 ? GCD(b, a % b) : a; }
long long LCM(long long a, long long b) { return a * (b / GCD(a, b)); }
long long Pow(long long n, long long e) {
  if (e == 0) return 1;
  if (e == 1)
    return n;
  else if (e & 1) {
    long long t = Pow(n, e / 2);
    return n * t * t;
  } else {
    long long t = Pow(n, e / 2);
    return t * t;
  }
}
const long long MOD = 1000000007;
long long PowMod(long long n, long long e, long long m) {
  if (e == 0) return 1;
  if (e == 1)
    return n % m;
  else if (e & 1) {
    long long t = PowMod(n, e / 2, m) % m;
    return (((t * t) % m) * (n % m)) % m;
  } else {
    long long t = PowMod(n, e / 2, m) % m;
    return (t * t) % m;
  }
}
long long C(long long n, long long k) {
  if (n == k || k == 0) return 1;
  if (k > n / 2) k = n - k;
  long long a = 1;
  for (int i = (1), max_ = (k + 1); i < max_; ++i) {
    a = (a * (n - i + 1)) % MOD;
  }
  long long b = 1;
  for (int i = (1), max_ = (k + 1); i < max_; ++i) {
    b = (b * i) % MOD;
  }
  a = (a * PowMod(b, MOD - 2, MOD)) % MOD;
  return a;
}
long long a[2005], r[2005], inv[2005];
int main() {
  int N, K;
  scanf("%d %d", &N, &K);
  for (int i = 0, max_ = (N); i < max_; ++i) scanf("%d", &a[i]);
  if (K == 0) {
    for (int i = 0, max_ = (N); i < max_; ++i) r[i] = a[i];
  } else {
    for (int i = (1), max_ = (2005); i < max_; ++i)
      inv[i] = PowMod(i, MOD - 2, MOD);
    r[0] = a[0];
    for (int i = (1), max_ = (N); i < max_; ++i) {
      r[i] = a[i];
      long long curr = K;
      int n = K;
      int k = 1;
      int j = i - 1;
      while (j >= 0) {
        long long tmp = (a[j] * curr) % MOD;
        r[i] = (r[i] + tmp) % MOD;
        ++n;
        ++k;
        curr = (curr * n) % MOD;
        curr = (curr * inv[k]) % MOD;
        --j;
      }
    }
  }
  for (int i = 0, max_ = (N); i < max_; ++i) printf("%I64d ", r[i]);
  return 0;
}
