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 inf = 1000000007;
const long long linf = 1LL << 62;
const unsigned long long ulinf = 1ULL << 63;
const double eps = 0.000001;
const double pi = 3.14159265358979323846;
template <class T>
T abs(T a) {
  return a >= 0 ? a : -a;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
T mod(T a, T b) {
  return (a % b + b) % b;
}
template <class T>
T addmod(T a, T b, T c) {
  return (T)mod((long long)a + b, (long long)c);
}
template <class T>
T mulmod(T a, T b, T c) {
  return (T)mod((long long)a * b, (long long)c);
}
template <class T>
T powmod(T a, T b, T c) {
  return (T)mod(
      b ? mulmod(mod(sqr((long long)powmod(a, b >> 1, c)), (long long)c),
                 (b & 1LL) ? a : 1LL, (long long)c)
        : 1LL,
      (long long)c);
}
template <class T>
void maxe(T &a, T b) {
  a = max(a, b);
}
template <class T>
void mine(T &a, T b) {
  a = min(a, b);
}
template <class T>
void mode(T &a, T b) {
  a = mod(a, b);
}
template <class T>
void addmode(T &a, T b, T c) {
  a = addmod(a, b, c);
}
template <class T>
void mulmode(T &a, T b, T c) {
  a = mulmod(a, b, c);
}
template <class T>
void powmode(T &a, T b, T c) {
  a = powmod(a, b, c);
}
int iszero(double a) { return abs(a) <= eps; }
template <class T>
void getint(T &a) {
  a = 0;
  int b = 1, c = getchar();
  if (c == '-')
    b = -1;
  else
    a = c - 48;
  while ((c = getchar()) != ' ' && c != '\n') a = a * 10 + c - 48;
  a *= b;
}
void fileio_in_out() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
void fileio_txt() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
}
const int N = 2222;
int test;
long long n, m, k, ans;
long long a[N], aa[N];
long long c[N];
const long long md = inf;
int main() {
  scanf("%I64d%I64d", &n, &k);
  for (long long i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  k--;
  c[0] = 1;
  for (long long i = 1; i <= n; i++)
    c[i] = mulmod(c[i - 1], mulmod(k + i, powmod(i, md - 2, md), md), md);
  for (long long i = 1; i <= n; i++)
    for (long long j = 0; j <= n - i; j++)
      addmode(aa[i + j], mulmod(a[i], c[j], md), md);
  for (long long i = 1; i <= n; i++) printf("%I64d ", aa[i]);
  return 0;
}
