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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

	/**
	 * @param args
	 */
	static int N, K;
	public static void main(String[] args) {
		InputReader r = new InputReader(System.in);
		
		N = r.nextInt();
		K = r.nextInt();
		
		int[] a = new int[N];
		for(int i = 0; i < N; i++)
			a[i] = r.nextInt();
		
		long[] ret = pow(K);
//		System.out.println(Arrays.toString(ret));
		
		for(int i = 0; i < N; i++){
			long ans = 0;

			for(int j = i; j >= 0; j--)
				ans = (ans + a[j] * ret[N - 1 - (i - j)]) % mod;
			
			System.out.println(ans);
		}
//		long[][] p = new long[N][N];
//		
//		for(long[] i : p)
//			Arrays.fill(i, 1);
//		for(int i = 0; i < N; i++)
//		for(int j = 0; j < N - i - 1; j++)
//			p[i][j] = 0;
//		
//		p = pow(p, K);
	}
	private static long[] pow(int p) {
		if(p == 0){
			long[] ret = new long[N];
			ret[N - 1] = 1;
			
			return ret;
		}else{
			if(p % 2 == 0){
				long[] ret = pow(p / 2);
//				System.out.println(Arrays.toString(ret));
				
				long[] now = new long[N];
				for(int i = N - 1; i >= 0; i--){
					for(int j = i; j < N; j++){
						int d = j - i;
						int o = N - 1 - d;
						
//						System.out.println(i + ": " + j + ", " + o);
						now[i] = (now[i] + ret[j] * ret[o]) % mod;
					}
				}
				
				return now;
					
			}else{
				long[] ret = pow(p - 1);
				
				long[] now = new long[N];
				now[N - 1] = 1;
				for(int i = N - 2; i >= 0; i--)
					now[i] = (now[i + 1] + ret[i]) % mod;
				
				return now;
			}
		}
	}
	//	private static long[][] pow(long[][] x, int p) {
//		if(p == 0){
//			long[][] ret = new long[x.length][x.length];
//			for(int i = 0; i < x.length; i++)
//				ret[i][i] = 1;
//			return ret;
//		}else{
//			if(p % 2 == 0){
//				long[][] ret = pow(x, p / 2);
//				return mul(ret, ret);
//			}else{
//				long[][] ret = pow(x, p - 1);
//				return mul(x, ret);
//			}
//		}
//	}
	static long mod = 1000000007;
//	private static long[][] mul(long[][] a, long[][] b) {
//		// TODO Auto-generated method stub
//		return null;
//	}
	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
				return null;
			}
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}
