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.*;
import java.util.*;
public class a {
public static void main(String[] args) throws IOException {
	input.init(System.in);
	PrintWriter out = new PrintWriter(System.out);
	int n = input.nextInt(), k = input.nextInt();
	long[] as = new long[n];
	for(int i = 0; i<n; i++)as[i] = input.nextLong();
	long[] choose = new long[n+1];
	choose[0] = 1;
	long mod = (long)(1e9+7);
	for(int i = 0; i<n; i++)
	{
		choose[i] = 1;
		for(int j = 0; j<i; j++)
		{
			choose[i] = (choose[i] * (i+k-j-1))%mod;
			choose[i] = (choose[i] * invmod(j+1, mod))%mod;
		}
	}
	//out.println(Arrays.toString(choose));
	for(int i = 0; i<n; i++)
	{
		long cur = 0;
		for(int j = 0; j<=i; j++)
		{
			cur = (cur + choose[j] * as[i-j])%mod;
		}
		out.print(cur+" ");
	}
	out.close();
}
//GCD - O(log(max(p, q)))
//res[0] is gcd of p and q
//res[1] and res[2] are values used in extended Euclidean algorithm for inverse mod
public static long[] gcd(long p, long q)
{
if(q==0)
	return new long[] {p, 1, 0};
long[] vals = gcd(q, p%q);
return new long[] {vals[0], vals[2], vals[1] - (p/q)*vals[2]};
}
//Inverse Mod - O(log(mod))
//Returns A s.t. x*A = 1(MOD mod)
public static long invmod(long x, long mod)
{
long[] vals = gcd(x, mod);
if(vals[0]>1)
	return -1;
if(vals[1]>0)
	return vals[1];
return mod + vals[1];
}
public static class input {
	static BufferedReader reader;
	static StringTokenizer tokenizer;

	static void init(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(reader.readLine());
		return tokenizer.nextToken();
	}

	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}
}
}

