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
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#define ll  long long
#define ull unsigned long long  
using namespace std;
#define  inf 1e15+18
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mod 1000000007
#define  f1(i,n) for(i=1;i<=n;i++)
#define f0(i,n)  for(i=0;i<n;i++)
#define w(x)   while(x--)
const int maxn=2000000;
#define  pq priority_queue
#define  ff first
#define  ss second 
#define pb  push_back
#define lb lower_bound
#define ld long double
#define ub upper_bound
#define LB 60
#define setp(x) cout<<fixed<<setprecision(x)
#define PQ_MIN  priority_queue <ll, vector<ll>, greater<ll> >
#define setbit(x)   __builtin_popcount(x)
#define all(x) (x).begin(),(x).end()
#define pie 3.14159265358
using large = int64_t;
ll gcd(ll int a,ll  int b,ll &x,ll &y)
{
    if (b == 0){
      x=1;
      y=0;
        return a;
      }
      ll x1,y1;
      ll d=gcd(b,a%b,x1,y1);
      x=y1;
      y=x1-y1*(a/b);
 return d;
    

}
ll power(ll n,ll p)
{
  ll r=1;
  while(p)
  {
    if(p&1)
    {
      r=(r*n)%mod;
      p--;
    }
    n=(n*n)%mod;
    p=p/2;
  }
  return r;
}

int main()
{
  fastio;
  int t;
 ll i,j,k,l,n,m=0,p=0;
 /* x,y,z;
  x,x+y  ,    x+y+z,x+y+z+t;
  x,2*x+y,3*x+2*y+z,4*x+3*y+2*z+t;
  x,3*x+y,6*x+3*y+z,10*x+6*y+3*z+t;
  x,4*x+y,10*x+4*y+z; 20*x+10*y+4*z+t
  x,5*x+y,15*x+5*y+z; 45*x+15*y+5*z+t
  x,6*x+y,21*x+6*y+z;
  */
   cin >>n>>k;
   ll a[n+2]={};
   for(i=1;i<=n;i++){
    cin >>a[i]; 
    if(!k)
      cout<<a[i]<<" ";
  }
  if(!k)
    return 0;
  ll b[n+2];
  b[1]=1;
  for(i=1;i<=n;i++)
  {
    b[i+1]=(b[i]*(i+k-1))%mod;
    b[i+1]=(b[i+1]*power(i,mod-2))%mod;
   // cout<<b[i]<<" ";
  }

    for(i=1;i<=n;i++)
    {
       m=1;
       l=0;
       for(j=i;j>=1;j--)
       {
          l+=(b[m]*a[j])%mod;
          m++;
       }
       cout<<l<<" ";
    }

}


   

