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 C138E
{

    private static StringTokenizer st;
    
    public static void nextLine(BufferedReader br) throws IOException
    {
        st = new StringTokenizer(br.readLine());
    }
    
    public static int nextInt()
    {
        return Integer.parseInt(st.nextToken());
    }
    
    public static String next()
    {
        return st.nextToken();
    }
    
    public static long nextLong()
    {
        return Long.parseLong(st.nextToken());
    }
    
    static final long MOD = 1000000007;
    static long[] MODI;
    /**
     * @param args
     */
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        nextLine(br);
        int n = nextInt();
        long k = nextLong();
        long[] a = new long[(int)n];
        nextLine(br);
        for (int i = 0; i < n; i++) a[i] = nextLong();
        MODI = new long[n+1];
        for (int i = 1; i <= n; i++) MODI[i] = modInverse(i, MOD);
        long[] coeff = new long[n];
        coeff[0] = 1;
        for (int i = 1; i < n; i++)
        {
            coeff[i] = choose(k+i-1, i);
        }
        long[] ans = new long[n];
        for (int i = 0; i < n; i++)
        {
            long sum = 0;
            for (int j = 0; j <= i; j++)
            {
                sum = moda(sum, modm(coeff[j], a[i-j]));
            }
            ans[i] = sum;
        }
        StringBuffer sb = new StringBuffer();
        sb.append(ans[0]);
        for (int i = 1; i < n; i++)
        {
            sb.append(" " + ans[i]);
        }
        //System.out.println(Arrays.toString(coeff));
        System.out.println(sb.toString());
    }
    
    public static long choose(long n, long k)
    {
        long num = 1;
        for (int i = 1; i <= k; i++)
        {
            num = modm(num, n-i+1);
            num = modm(num, MODI[i]);
        }
        return num;
    }
    
    public static long moda(long a, long b)
    {
        return (a + b) % MOD;
    }
    
    public static long modm(long a, long b)
    {
        return (a * b) % MOD;
    }
    
    private static long pow(long a, long b, long m) {
        long x = 1, y = a;
        while(b > 0) 
        {
            if(b % 2 == 1) 
            {
                x=(x*y);
                if(x > m) x%=m;
            }
            y = (y * y);
            if(y > m) y%=m;
            b /= 2;
        }
        return x;
    }

    private static long modInverse(long a, long m) {
        return pow(a,m-2,m);
    }
    
}
