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
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF223C extends PrintWriter {
	CF223C() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF223C o = new CF223C(); o.main(); o.flush();
	}

	static final int MD = 1000000007;
	static final int M0 = (56 << 23) + 1;
	static final int M1 = (71 << 23) + 1;
	static final int M2 = (77 << 23) + 1;
	static final int[] MD_ = { M0, M1, M2 };
	static final int V01 = (int) power(M0, M1 - 2, M1);
	static final int V02 = (int) power(M0, M2 - 2, M2);
	static final int V12 = (int) power(M1, M2 - 2, M2);
	static long power(int a, int k, int md) {
		if (k == 0)
			return 1;
		long p = power(a, k / 2, md);
		p = p * p % md;
		if (k % 2 == 1)
			p = p * a % md;
		return p;
	}
	int[] ww, ww_;
	void ntt(int[] aa, int n, int md, boolean inverse) {
		for (int i = 1, j = 0; i < n; i++) {
			int b = n;
			do
				j ^= b >>= 1;
			while ((j & b) == 0);
			if (i < j) {
				int tmp = aa[i]; aa[i] = aa[j]; aa[j] = tmp;
			}
		}
		for (int h = 0, b; (b = 1 << h) < n; h++) {
			int w = inverse ? ww_[h + 1] : ww[h + 1];
			long w_ = 1;
			for (int j = 0; j < b; j++) {
				for (int l = j; l < n; l += b * 2) {
					int r = l + b;
					long u = aa[l], v = aa[r] * w_;
					aa[l] = (int) ((u + v) % md);
					aa[r] = (int) ((u - v) % md);
				}
				w_ = w_ * w % md;
			}
		}
	}
	int garner(int r0, int r1, int r2) {
		if (r0 < 0)
			r0 += M0;
		r1 = (int) ((long) (r1 - r0) * V01 % M1);
		if (r1 < 0)
			r1 += M1;
		r2 = (int) (((long) (r2 - r0) * V02 - r1) % M2 * V12 % M2);
		if (r2 < 0)
			r2 += M2;
		return (int) ((((long) r2 * M1 + r1) % MD * M0 + r0) % MD);
	}
	void main() {
		int n = sc.nextInt();
		int k = sc.nextInt();
		int h_ = 1;
		while (1 << h_ < n)
			h_++;
		h_++;
		int n_ = 1 << h_;
		int[] aa = new int[n_];
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt();
		int[] ch = new int[n_];
		ch[0] = 1;
		for (int i = 1; i < n; i++)
			ch[i] = (int) ((long) ch[i - 1] * (k - 1 + i) % MD * power(i, MD - 2, MD) % MD);
		ww = new int[h_ + 1];
		ww_ = new int[h_ + 1];
		int[] pp = new int[n_];
		int[] qq = new int[n_];
		int[][] rr = new int[3][n_];
		for (int z = 0; z < 3; z++) {
			int md = MD_[z];
			long v = power(n_, md - 2, md);
			for (int h = 0; h <= h_; h++) {
				ww[h] = (int) power(3, md - 1 >> h, md);
				ww_[h] = (int) power(3, md - 1 - (md - 1 >> h), md);
			}
			for (int i = 0; i < n_; i++) {
				pp[i] = aa[i];
				qq[i] = ch[i];
			}
			ntt(pp, n_, md, false);
			ntt(qq, n_, md, false);
			for (int i = 0; i < n_; i++)
				rr[z][i] = (int) ((long) pp[i] * qq[i] % md);
			ntt(rr[z], n_, md, true);
			for (int i = 0; i < n_; i++)
				rr[z][i] = (int) (rr[z][i] * v % md);
		}
		for (int i = 0; i < n; i++)
			print(garner(rr[0][i], rr[1][i], rr[2][i]) + " ");
		println();
	}
}
