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

import java.math.BigInteger;
import java.util.*;

public class C{

    long mod=1000000007;

    void solve()throws Exception
    {
        int n=nextInt();
        int k=nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=nextInt();
        if(k==0)
        {
            printIt(a);
            return;

        }
        long[]v=new long[n];
        for(int i=0;i<n;i++)
            v[i]=C(i+k-1,k-1);
        long[]res=new long[a.length];
        for(int i=0;i<n;i++)
            for(int j=i;j<n;j++)
            {
                res[j]+=v[j-i]*a[i];
                res[j]%=mod;
            }
        printIt2(res);

    }

    private void printIt(int[] a) {
        for(int i=0;i<a.length;i++)
        {
            if(i==a.length-1)
                writer.println(a[i]);
            else
                writer.print(a[i]+" ");
        }
    }
    private void printIt2(long[] a) {
        for(int i=0;i<a.length;i++)
        {
            if(i==a.length-1)
                writer.println(a[i]);
            else
                writer.print(a[i]+" ");
        }
    }


    long C(long n,long k)
    {
        if(k>n)
            return 0;
        k=Math.min(k, n - k);
        long res=1;
        long dom=1;
        for(int i=1;i<=k;i++)
        {
            dom=dom*i%mod;
            res=res*(n-i+1)%mod;
        }
        return res* BigInteger.valueOf(dom).modInverse(BigInteger.valueOf(mod)).longValue()%mod;
    }

    ////////////
    BufferedReader reader;
    PrintWriter writer;
    StringTokenizer stk;
    void run()throws Exception
    {

        reader=new BufferedReader(new InputStreamReader(System.in));
        //reader=new BufferedReader(new FileReader("3.in"));
        stk=null;
        writer=new PrintWriter(new PrintWriter(System.out));
        //writer=new PrintWriter(new FileWriter("output.txt"));
        solve();
        reader.close();
        writer.close();
    }
    int nextInt()throws Exception
    {
        return Integer.parseInt(nextToken());
    }

    long nextLong()throws Exception
    {
        return Long.parseLong(nextToken());

    }
    double nextDouble()throws Exception
    {
        return Double.parseDouble(nextToken());


    }

    String nextString()throws Exception
    {
        return nextToken();
    }
    String nextLine()throws Exception
    {
        return reader.readLine();
    }
    String nextToken()throws Exception
    {
        if(stk==null || !stk.hasMoreTokens())
        {
            stk=new StringTokenizer(nextLine());
            return nextToken();

        }
        return stk.nextToken();
    }

    public static void main(String[]args) throws Exception
    {
        new C().run();
    }








}
