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.*;

public class Main {
	private static int[] pow(int[] a, int k) {
		if (k == 0) {
			int[] res = new int[a.length];
			res[0] = 1;
			return res;
		} else if (k % 2 == 0) {
			return pow(mul(a, a), k / 2);
		} else {
			return mul(a, pow(a, k - 1));
		}
	}

	private static int[] mul(int[] a, int[] b) {
		int[] c = new int[a.length];
		for (int i = 0; i < a.length; ++i) {
			long r = 0;
			for (int j = 0; j <= i; ++j) {
				r += a[j] * (long) b[i - j];
				if (r > 6e18)
					r %= 1e9 + 7;
			}
			c[i] = (int) (r % (1e9 + 7));
		}
		return c;
	}

	public static void main(String[] args) throws IOException {
		Reader in = new Reader(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		int[] m = new int[n];
		for (int i = 0; i < n; i++) {
			m[i] = 1;
		}
		m = pow(m, k);
		a = mul(a, m);
		for (int i = 0; i < n; ++i) {
			if (i > 0)
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();

	}

}

class Reader {
	private BufferedReader x;
	private StringTokenizer st;

	public Reader(InputStream in) {
		x = new BufferedReader(new InputStreamReader(in));
		st = null;
	}

	public String nextString() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(x.readLine());
		return st.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextString());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextString());
	}
}