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
//pb_ds 20160123_4
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <cmath>
using namespace std;
#define RG register
#define set_file(File) freopen(File ".in", "r", stdin), freopen(File ".out", "w", stdout)
#define close_file() fclose(stdin), fclose(stdout)
#define For(i, a, b) for(RG int i = a, ___u = b; i <= ___u; ++i)
#define ForDown(i, a, b) for(RG int i = b, ___d = a; i >= ___d; --i)
#define cmax(i, j) ((i) < (j) ? (i) = (j) : (i))
#define cmin(i, j) ((i) > (j) ? (i) = (j) : (i))
#define dmax(i, j) ((j) < (i) ? (i) : (j))
#define dmin(i, j) ((i) < (j) ? (i) : (j))
#define ddel(i, j) ((i) > (j) ? (i) - (j) : (j) - (i))
#define dabs(i) ((i) > 0 ? (i) : -(i))
#define dsqr(x) ((x) * (x))
#define lowbit(i) ((i) & -(i))
typedef long long ll;
typedef double db;
typedef long double ld;
 
namespace io
{
	const int MAXBUF = 1 << 15;
	const int OUTPUT = 1 << 23;
	char b[MAXBUF], *S = b, *T = b;
	#define getc() (S == T && (T = (S = b) + fread(b, 1, MAXBUF, stdin), S == T) ? 0 : *S++)
	#define fastcall __attribute__((optimize("-O3")))
	#define IL __inline__ __attribute__((always_inline))
	template<class Type> IL Type read()
	{
		RG Type aa = 0; RG bool bb = 0; RG char ch, *S = io::S, *T = io::T;
		for(ch = getc(); (ch < '0' || ch > '9') && ch != '-'; ch = getc())
			;
		for(ch == '-' ? bb = 1 : aa = ch - '0', ch = getc(); '0' <= ch && ch <= '9'; ch = getc())
			aa = aa * 10 + ch - '0';
		io::S = S, io::T = T; return bb ? -aa : aa;
	}
	int (*F)() = read<int>;
	template<> IL double read()
	{
		RG double aa = 0, bb;
		RG bool cc = 0;
		RG char ch;
		RG char *S = io::S, *T = io::T;
		for(ch = getc(); (ch < '0' || ch > '9') && ch != '-'; ch = getc())
			;
		for(ch == '-' ? cc = 1 : aa = ch - '0', ch = getc(); '0' <= ch && ch <= '9'; ch = getc())
			aa = aa * 10 + ch - '0';
		if(ch == '.')
		{
			bb = 1;
			while(ch = getc(), ch >= '0' && ch <= '9')
				aa += (bb *= 0.1) * (ch - '0');
		}
		io::S = S, io::T = T;
		return cc ? -aa : aa;
	}

	IL int gets(RG char *s)
	{
		RG char *iter = s, *S = io::S, *T = io::T;
		while(*iter = getc(), *iter == ' ' || *iter == '\n' || *iter == '\r')
			;
		while(*++iter = getc(), *iter != ' ' && *iter != '\n' && *iter != '\r')
			;
		*iter = 0;		
		io::S = S, io::T = T;
		return iter - s;
	}
	IL char get()
	{
		RG char ch;
		while(ch = getc(), ch == ' ' || ch == '\n' || ch == '\r')
			;
		return ch;
	}
	
	char buff[OUTPUT], *iter = buff;
	template<class T>IL void P(RG T x, RG char ch = '\n')
	{
///*lgg*/cout << x << ch; return;
		static int stack[110]; RG int O = 0; RG char *iter = io::iter;
		if(!x)*iter++ = '0';
		else
		{
			(x < 0) ? x = -x, *iter++ = '-' : 1;
			for(; x; x /= 10) stack[++O] = x % 10;
			for(; O; *iter++ = '0' + stack[O--])
				;
		}
		*iter++ = ch, io::iter = iter;
	}

	IL void puts(RG const char *s) {while(*s) *iter++ = *s++;}
	IL void output() {fwrite(buff, 1, iter - buff, stdout), iter = buff;}
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
//typedef __float128 lld;

namespace pb_ds
{
	const int MAXN = 2010;
	int a[MAXN], b[MAXN];
	IL int inver(RG int a)
	{
		static const int mod = 1e9 + 7;
		RG int ans = 1;
		for(RG int b = mod - 2; b; b >>= 1)
		{
			if(b % 2) ans = (ll) ans * a % mod;
			a = (ll) a * a % mod;
		}
		return ans;
	}
	namespace FNT
	{
		const ll mod = 1945555039024054273ll;
		#define shr(x) ((x) >> 32)
		#define tail(x) ((x) & cut)
		#define shl(x) ((x) << 32)
		const int MAXN = 4100;
		ll a[MAXN], b[MAXN], c[MAXN], w[2][MAXN];
		int rev[MAXN];
		IL ll mul(RG const ll& a, RG const ll& b)
		{
			RG ll q = (ll) ((__float128) a * b / mod);
			RG ll r = a * b - q * mod;
			while(r < 0) r += mod;
			return r;
		}
		IL ll power(RG ll a, RG ll b)
		{
			RG ll ans = 1;
			for(; b; b >>= 1)
			{
				if(b % 2) ans = mul(ans, a);
				a = mul(a, a);
			}
			return ans;
		}
		IL void DFT(RG int n, RG ll *a, RG ll *w)
		{
			RG ll tmp;
			RG int i, j, k, l, s, t;
			for(i = 0; i < n; ++i) if(i > rev[i])
				tmp = a[i], a[i] = a[rev[i]], a[rev[i]] = tmp;
			for(i = 2; i <= n; i <<= 1)
			for(s = n / i, l = i >> 1, j = 0; j < n; j += i)
			for(k = j, t = 0; k < j + l; t += s, ++k)
			{
				tmp = mul(a[k + l], w[t]);
				(a[k + l] = a[k] - tmp) < 0 ? a[k + l] += mod : 1;
				(a[k] += tmp) >= mod ? a[k] -= mod : 1;
			}

		}
		#define G(i) ((ll)(i))
		IL void convol(RG int n)
		{
			RG int l = __builtin_ctz(n) - 1;
///*lgg*/assert(n == (1 << l));
			static const int _g = 5;
			RG ll g = power(_g, (mod - 1) / n);
///*lgg*/printf("g = %lld\n", g);
			w[0][0] = w[1][0] = 1;
			For(i, 1, n - 1)
			{
				w[1][n - i] = w[0][i] = mul(g, w[0][i - 1]);
				rev[i] = (rev[i >> 1] >> 1) | ((i % 2) << l);
			}
///*lgg*/for(int i=0;i<n;++i)printf("i = %d rev = %d a = %lld b = %lld w = %lld %lld\n",i,rev[i], G(a[i]),G(b[i]),G(w[0][i]),G(w[1][i]));
 			DFT(n, a, w[0]), DFT(n, b, w[0]);
///*lgg*/for(int i=0;i<n;++i)printf("i = %d a = %lld b = %lld\n",i,G(a[i]),G(b[i]));
			For(i, 0, n - 1) c[i] = mul(a[i], b[i]);
			DFT(n, c, w[1]);
			RG ll temp = power((ll)n, mod - 2);
			For(i, 0, n - 1) 
			{
///*lgg*/printf("%lld %lld %lld\n",temp,c[i],mul(c[i],temp));
				c[i] = mul(c[i], temp);
			}
		}
		//typedef __int128 lll;
	}
	
	IL void main()
	{
		RG int (*F)() = io::read<int>;
		RG const int mod = 1e9 + 7;
		RG int n = F(), k = F() - 1;
		For(i, 0, n - 1) a[i] = F();
		b[0] = 1;	//b[i] = {k + i \choose i}
		For(i, 1, n - 1) b[i] = (ll) b[i - 1] * (k + i) % mod * inver(i) % mod;
///*lgg*/For(i,0,n-1)printf("b[%d] = %d\n", i, b[i]);
		RG int Tn = 1;
		while(Tn < n) Tn <<= 1;
		Tn <<= 1;
		For(i, 0, n - 1) FNT::a[i] = (a[i]), FNT::b[i] = (b[i]);
		FNT::convol(Tn);
		For(i, 0, n - 1) io::P(int(FNT::c[i] % mod), " \n"[i == ___u]);
	}
}

int main()
{
	//set_file("travel");
	pb_ds::main();
	io::output();
	close_file();
}
/*
10 100
1 2
2 3
2 4
2 5
2 6
5 7
1 8
8 9
1 10
^/\*lgg\*/
