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
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define rep(i,a,b) for (rg int i=(a);i<=(b);i++)
#define per(i,a,b) for (rg int i=(b);i>=(a);i--)
#define pb push_back
#define lowbit(x) (x&(-x))
#define mk make_pair
#define VI vector<int>
#define pii pair<int,int>
#define pLL pair<long long,long long>
#define fi first
#define se second
#define il inline
#define ll long long
#define db double
#define ld long double
#define inf 0x3f3f3f3f
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<15,stdin),p1==p2)?EOF:*p1++)
char buf[1<<15],*p1 = buf,*p2 = buf;
inline ll read(){
    #define num ch-'0'
    char ch;bool flag=0;ll res;
    while(!isdigit(ch=getc()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getc());res=res*10ll+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
inline void write(ll x){
	if (x < 0) x = ~x + 1ll, putchar('-');
	if (x > 9) write(x / 10ll);
	putchar(x % 10ll + '0');
}
#define mid ((l + r)>>1)
#define ls (x<<1)
#define rs ((x<<1)|1)
#undef mid
#undef ls
#undef rs
#define maxn 2020
const ll mod = 1e9 + 7;
struct node{
	ll a[maxn][maxn];
	int n,m;
	node(int nn,int mm){memset(a,0,sizeof(a));
	n = nn;
	m = mm;
	}
	void one()
	{
		rep(i,1,n) a[i][i] = 1;
	}
	void build()
	{
		rep(i,1,n)
		{
			rep(j,1,i)
			{
				a[j][i] = 1;
			}
		}
	}
	node operator * (node b)
	{
		node c(n,b.m);
		rep(i,1,n)
		{
			rep(j,1,b.m)
			{
				rep(k,1,m)
				{
					c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
				}
			}
		}
		return c;
	}
};
ll a[maxn];
void solve()
{
	int n = read();int K = read();
	rep(i,1,n) a[i] = read();
	node c(n,n),ans(n,n);
	c.build();
	ans.one();
	while(K)
	{
		if(K&1) ans = ans * c;
		c = c * c;
		K >>=1;
	}
	rep(i,1,n)
	{
		ll res = 0;
		rep(k,1,n)
		res = (res + a[k] * ans.a[i][k] % mod) % mod;
		cout<<res<<" ";
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("data.txt","r",stdin);
	#endif
//	int T = read();
//	while(T--)
	solve();
}