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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class E224 
{
    static class Scanner
    {
        BufferedReader br;
        StringTokenizer tk=new StringTokenizer("");
        public Scanner(InputStream is) 
        {
            br=new BufferedReader(new InputStreamReader(is));
        }
        public int nextInt() throws IOException
        {
            if(tk.hasMoreTokens())
                return Integer.parseInt(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return Integer.parseInt(tk.nextToken());
        }
        public long nextLong() throws IOException
        {
            if(tk.hasMoreTokens())
                return Long.parseLong(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return Long.parseLong(tk.nextToken());
        }
        public String next() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return (tk.nextToken());
        }
        public String nextLine() throws IOException
        {
            tk=new StringTokenizer("");
            return br.readLine();
        }
        public double nextDouble() throws IOException
        {
            if(tk.hasMoreTokens())
                return Double.parseDouble(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return Double.parseDouble(tk.nextToken());
        }
        public char nextChar() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken().charAt(0));
            tk=new StringTokenizer(br.readLine());
            return (tk.nextToken().charAt(0));
        }
    
    
    
    }
    static long mod=1000000007;
    static void multiply(long a[],long[] b,int n)
    {
        int ofs=n;
        long c[]=new long[n];
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                c[j]+=a[i]*b[j-i];
                c[j]%=mod;
            }
        }
        for(int i=0;i<n;i++)
            a[i]=c[i];
    }
    static void find(long a[],int k)
    {
        if(k==0)
            return;
        int n=a.length;
        long b[]=new long[n];
        Arrays.fill(b,1);
        long c[]=new long[n];
        c[0]=1;
        while(k>0)
        {
            if(k%2==1)
            {
                multiply(c,b,n);
            }
            k/=2;
            multiply(b,b,n);
        }
        multiply(a,c,n);
    }
    public static void main(String args[]) throws IOException
    {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        long a[]=new long[n];
        for(int i=0;i<n;i++)
            a[i]=in.nextInt();
        find(a,k);
        for(int i=0;i<n;i++)
            System.out.print(a[i]+" ");
        System.out.println();
                    
    }

}
