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.lang.*;
import java.math.*;
import java.io.*;
import java.util.*;
 
public class Solution implements Runnable {
	public static BufferedReader br;
	public static PrintWriter out;
	public static StringTokenizer stk;
	public static boolean isStream = true;
	
	public static void main(String[] args) throws IOException {
		if (isStream) {
	        br = new BufferedReader(new InputStreamReader(System.in));
	    } else {
	        br = new BufferedReader(new FileReader("in4.txt"));
	    }
	    out = new PrintWriter(System.out);
	    new Solution().run();
	}
	
	public void loadLine() {
	    try {
	        stk = new StringTokenizer(br.readLine());
	    } catch (IOException e) {
	        e.printStackTrace();
	    }
	}
	
	public String nextLine() {
	    try {
	        return br.readLine();
	    } catch (IOException e) {
	        e.printStackTrace();
	        return "";
	    }
	}
	
	public String nextWord() {
	    while (stk==null||!stk.hasMoreTokens()) loadLine();
	    return stk.nextToken();
	}
	
	public Integer nextInt() {
	    while (stk==null||!stk.hasMoreTokens()) loadLine();
	    return Integer.valueOf(stk.nextToken());
	}
	
	public Long nextLong() {
	    while (stk==null||!stk.hasMoreTokens()) loadLine();
	    return Long.valueOf(stk.nextToken());
	}
	
	public Double nextDouble() {
	    while (stk==null||!stk.hasMoreTokens()) loadLine();
	    return Double.valueOf(stk.nextToken());
	}
	
	public Float nextFloat() {
	    while (stk==null||!stk.hasMoreTokens()) loadLine();
	    return Float.valueOf(stk.nextToken());
	}
	    
	long MOD = 1000000007;
	int n;
	
	long[] mul(long[] a, long[] b) {
		long[] res = new long[n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				res[i] += a[j]*b[i-j];
				res[i] %= MOD;
			}
		}
		return res;
	}
	
	long[] pow(long[] a, int k) {
		if (k == 1) return a;
		if (k%2 == 0) {
			long[] res = mul(a, a);
			return pow(res, k/2);
		} else {
			return mul(a, pow(a, k-1));
		}
	}
	
	public void run() {
		n = nextInt();
		int k = nextInt();
		long[] arr = new long[n];
		long[] cur = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = nextInt();
			cur[i] = 1;
		}
		long[] res = k==0?arr:mul(arr, pow(cur, k));
		for (int i = 0; i < n; i++) {
			out.print(res[i] % MOD);
			out.print(' ');
		}
		out.println();
	    out.flush();
	}
}