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

public class partialsums {
	static long MOD = 1000000007;

	static class FFT {
		static final int maxk = 21, maxn = (1 << maxk) + 1;
		// Init: wR, wI, rR, rI, aR, aI   to   new double[maxn] !!!
		//#
		static double[] wR = new double[maxn],
				wI = new double[maxn],
				rR = new double[maxn],
				rI = new double[maxn],
				aR  = new double[maxn],
				aI  = new double[maxn]; //$
		static int n, k, lastk = -1, dp[] = new int[maxn];

		static void fft(boolean inv) {
			if (lastk != k) {
				lastk = k;  dp[0] = 0;
				for (int i = 1, g = -1; i < n; i++) {
					if ((i & (i - 1)) == 0) g++;
					dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
				}
				wR[1] = 1;
				wI[1] = 0;
				for (int t = 0; t < k - 1; t++) {
					double a = Math.PI / n * (1 << (k - 1 - t));
					double curR = Math.cos(a), curI = Math.sin(a);
					int p2 = (1 << t), p3 = p2 * 2;
					for (int j = p2, k = j * 2; j < p3; j++, k += 2) {
						wR[k] = wR[j];
						wI[k] = wI[j];
						wR[k + 1] = wR[j] * curR - wI[j] * curI;
						wI[k + 1] = wR[j] * curI + wI[j] * curR;
					}
				}
			}
			for (int i = 0; i < n; i++) {
				int d = dp[i];
				if (i < d) {
					double tmp = aR[i];
					aR[i] = aR[d];
					aR[d] = tmp;
					tmp = aI[i];
					aI[i] = aI[d];
					aI[d] = tmp;
				}
			}
			if (inv) for (int i = 0; i < n; i++) aI[i] = -aI[i];
			for (int len = 1; len < n; len <<= 1) {
				for (int i = 0; i < n; i += len) {
					int wit = len;
					for (int it = 0, j = i + len; it < len; it++, i++, j++) {
						double tmpR = aR[j] * wR[wit] - aI[j] * wI[wit];
						double tmpI = aR[j] * wI[wit] + aI[j] * wR[wit];
						wit++;
						aR[j] = aR[i] - tmpR;
						aI[j] = aI[i] - tmpI;
						aR[i] += tmpR;
						aI[i] += tmpI;
					}
				}
			}
		}

		static long[] multiply(long[] a, long[] b) {
			int na = a.length, nb = b.length;
			for (k = 0, n = 1; n < na + nb - 1; n <<= 1, k++) {}
			for (int i = 0; i < n; ++i) {
				aR[i] = i < na ? a[i] : 0;
				aI[i] = i < nb ? b[i] : 0;
			}
			fft(false);
			aR[n] = aR[0];
			aI[n] = aI[0];
			double q = -1.0 / n / 4.0;
			for (int i = 0; i <= n - i; ++i) {
				double tmpR = aR[i] * aR[i] - aI[i] * aI[i];
				double tmpI = aR[i] * aI[i] * 2;
				tmpR -= aR[n - i] * aR[n - i] - aI[n - i] * aI[n - i];
				tmpI -= aR[n - i] * aI[n - i] * -2;
				aR[i] = -tmpI * q;
				aI[i] = tmpR * q;
				aR[n - i] = aR[i];
				aI[n - i] = -aI[i];
			}
			fft(true);
			long[] ans = new long[n = na + nb - 1]; // ONLY MOD IF NEEDED
			for (int i = 0; i < n; i++) ans[i] = Math.round(aR[i]) % MOD;
			return ans;
		}

		static long[] multiplyPrecise(long[] a, long[] b) {
			long k = (long)(Math.sqrt(MOD));
			long[] a1 = new long[a.length], a2 = new long[a.length];
			long[] b1 = new long[b.length], b2 = new long[b.length];
			for(int i=0;i<a.length;i++) {
				a1[i] = a[i] % k;
				a2[i] = a[i] / k;
			}
			for(int i=0;i<b.length;i++) {
				b1[i] = b[i] % k;
				b2[i] = b[i] / k;
			}
			long[] r11 = multiply(a1, b1), r12 = multiply(a1, b2), r21 = multiply(a2, b1), r22 = multiply(a2, b2);
			long[] res = new long[r11.length];
			for(int i=0;i<res.length;i++)
				res[i] = (k*k*r22[i] + k*(r12[i] + r21[i]) + r11[i]) % MOD;
			return res;
		}
	}

	public static long[] ones(int length) {
		long[] arr = new long[length];
		Arrays.fill(arr, 1);
		return arr;
	}

	public static long[] trunc(long[] poly, int length) {
		long[] arr = new long[length];
		for (int i=0; i<length; i++) arr[i] = poly[i];
		return arr;
	}

	public static long[] fFFTexpo(long[] poly, int exp) {
		if (exp == 1) return ones(poly.length);
		if (exp%2 == 0) {
			long[] mult = fFFTexpo(poly, exp/2);
			return trunc(FFT.multiplyPrecise(mult, mult), poly.length);
		}
		// return trunc(FFT.multiplyPrecise(poly, fFFTexpo(poly, exp-1)), poly.length);
		long[] mult = fFFTexpo(poly, exp/2);
		mult = trunc(FFT.multiplyPrecise(mult, mult), poly.length);
		return trunc(FFT.multiplyPrecise(mult, poly), poly.length);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(), k = sc.nextInt();
		long[] arr = new long[n];

		for (int i=0; i<n; i++) arr[i] = sc.nextLong();

		if (k != 0) {
			long[] poly = ones(n);

			poly = fFFTexpo(poly, k);
			arr = trunc(FFT.multiplyPrecise(poly, arr), n);
		}

		for (int i=0; i<n; i++) {
			if (i == 0) System.out.print(arr[i]);
			else System.out.printf(" %d", arr[i]);
		}
		System.out.println();
	}
}