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
import java.util.*;

public class Main {

  public static void main(String args[]) {
    (new Main()).solve();
  }

  int mod = 1000 * 1000 * 1000 + 7;

  int com(int K, int C) {
    long ret = 1;
    long div = 1;
    for(int i=1; i<=C; ++i) {
      ret = ret * (K - i + 1) % mod;
      div = div * i % mod;
    }
    return (int)(ret * pow(div, mod - 2) % mod);
  }

  long pow(long a, int p) {
    if( p == 0 ) { return 1; }
    if( p % 2 == 0 ) { return pow(a * a % mod, p / 2); }
    return pow(a * a % mod, p / 2) * a % mod;
  }

  void solve() {

    Scanner cin = new Scanner(System.in);

    int N = cin.nextInt();
    int K = cin.nextInt();

    int vec[] = new int[N];
    for(int i=0; i<N; ++i) { vec[i] = cin.nextInt(); }

    int mat[][] = new int[N][N];
    for(int i=0; i<N; ++i) {
      for(int j=i; j<N; ++j) {
        if( i == 0 ) {
          mat[i][j] = com(K + (j - i - 1), j - i);
        }
        else {
          mat[i][j] = mat[i - 1][j - 1];
        }
      }
    }

    Matrix matrix = new Matrix(mod);
    int res[] = matrix.mult(vec, mat, N);
    for(int i=0; i<N; ++i) {
      if( i > 0 ) { System.out.print(" "); }
      System.out.print(res[i]);
    }
    System.out.println();

  }

class Matrix {

  private int mod;
  private long thres;

  public Matrix(int mod) {
    this.mod = mod;
    thres = Long.MAX_VALUE - (long)(mod) * mod;
  }

  private int[][] base(int N) {
    int ret[][] = new int[N][N];
    for(int i=0; i<N; ++i) { ret[i][i] = 1; }
    return ret;
  }

  public int[][] pow(int a[][], int N, int P) {
    int ret[][] = base(N);
    while( P > 0 ) {
      if( (P & 1) == 1 ) { ret = mult(ret, a, N); }
      P /= 2;
      if( P > 0 ) { a = mult(a, a, N); }
    }
    return ret;
  }

  public int[][] mult(int a[][], int b[][], int N) {
    int c[][] = new int[N][N];
    for(int i=0; i<N; ++i) {
      for(int j=0; j<N; ++j) {
        long sum = 0;
        for(int k=0; k<N; ++k) {
          sum += (long)(a[i][k]) * b[k][j];
          if( sum > thres ) { sum %= mod; }
        }
        if( sum >= mod ) { sum %= mod; }
        c[i][j] = (int)(sum);
      }
    }
    return c;
  }

  public int[] mult(int a[], int b[][], int N) {
    int c[] = new int[N];
    for(int i=0; i<N; ++i) {
      long sum = 0;
      for(int j=0; j<N; ++j) {
        sum += (long)(a[j]) * b[j][i];
        if( sum > thres ) { sum %= mod; }
      }
      if( sum >= mod ) { sum %= mod; }
      c[i] = (int)(sum);
    }
    return c;
  }

}


}
