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.io.InputStreamReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.io.Writer;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
	public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.nextInt(), K = in.nextInt();
        long mod = (long) (1e9+7);
        int a[] = in.nextIntArray(n);
        int i,j;
        
        long c[] = new long[n];
        c[0] = 1;
        if(K>0)
        for(i=1;i<n;++i) c[i] = c[i-1]*(i+K-1)%mod*NumUtils.modInverse(i,mod)%mod;
        
        
        long d[] = new long[n];
        for(i=0;i<n;++i){
            for(j=0;j<=i;++j) d[i] = (d[i] + a[j]*c[i-j])%mod;
        }
        
        for(i=0;i<n;++i) out.write(d[i],' ');
	}
}

class InputReader{
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    
    public InputReader(InputStream stream){
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    
    public String next(){
        while(tokenizer==null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    
    public int nextInt(){
        return Integer.parseInt(next());
    }

    public int[] nextIntArray(int size){
        int array[] = new int[size];
        for(int i=0; i<size; ++i) array[i] = nextInt();
        return array;
    }
}

class OutputWriter{
    private PrintWriter out;
    
    public OutputWriter(Writer out){
        this.out = new PrintWriter(out);
    }

    public OutputWriter(OutputStream out){
        this.out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
    }
    
    public void close(){
        out.close();
    }

    public void write(Object ... o){
        for(Object x : o) out.print(x);
    }

    }

class NumUtils {
    
    public static long  modInverse(long a, long mod){
        long r, q, x0, x1, x, b = mod;
        x0=1; x1=x=0;
        a = (a%mod+mod)%mod;
        while(b!=0){
            r = a%b;
            q = a/b;
            if(r!=0){
                x = x0-q*x1;
                x0 = x1;
                x1 = x;
            }
            a = b; b = r;
        }
        x=(x%mod+mod)%mod;
        return x;
    }

    }

