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.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Locale;
import java.util.StringTokenizer;
import java.util.regex.Pattern;

public class Solution implements Runnable {
    public static void main(String[] args) {
        new Solution().run();
    }
    
    final int USE_FILES = 1;
    final int USE_STDIO = 0;
    final int DEFAULT = -1;
    int IO_MODE = DEFAULT;
    BufferedReader br;
    PrintWriter out;
    StringTokenizer in;
    
    public String nextToken() throws Throwable {
        while (in == null || !in.hasMoreTokens())
            in = new StringTokenizer(br.readLine());
        return in.nextToken();
    }
    
    public int nextInt() throws Throwable {
        return Integer.parseInt(nextToken());
    }
    
    public long nextLong() throws Throwable {
        return Long.parseLong(nextToken());
    }
    
    public double nextDouble() throws Throwable {
        return Double.parseDouble(nextToken());
    }
    
    long[] Identity;
    final long MOD = 1000000007;
    
    long[] matrix_mult(long[] a, long[] b) {
        int n = a.length;
        assert(n == b.length);
        long[] c = new long[n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++)
                c[i] = (c[i] + a[j] * b[i - j]) % MOD;
        return c;
    }
    
    long[] binpow(long[] a, int n) {
        long[] res = Identity.clone();
        while (n > 0) {
            if ((n & 1) == 1)
                res = matrix_mult(res, a);
            a = matrix_mult(a, a);
            n >>= 1;
        }
        return res;
    }
    
    int solve() throws Throwable {
        int n = nextInt();
        int k = nextInt();
        
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        Identity = new long[n];
        for (int i = 0; i < Identity.length; i++)
            Identity[i] = 1;
        
        long[] q = Identity.clone();
        long[] ans = new long[n];
        
        if (k != 0) {
            q = binpow(q, k - 1);
            for (int i = 0; i < ans.length; i++)
                for (int j = 0; j <= i; j++)
                    ans[i] = (ans[i] + a[j] * q[i - j]) % MOD;
        } else {
            for (int i = 0; i < n; i++)
                ans[i] = a[i];
        }
        
        for (int i = 0; i < n; i++)
            out.print(ans[i] + " ");
        
        return 0;
    }
    
    public void run() {
        boolean ONLINE_JUDGE = false;
        try {
            long startTime = System.currentTimeMillis();
            
            try {
                ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
                Locale.setDefault(Locale.US);       
            } catch (Throwable t) {
                System.err.println("Operation is forbidden");
            }
            
            if (IO_MODE == USE_FILES || (IO_MODE == DEFAULT && !ONLINE_JUDGE)) {
                br = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            } else {
                br = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            }
            
            int ret = solve();
            br.close();
            out.close();
            
            long endTime = System.currentTimeMillis();
            long freeMemory = Runtime.getRuntime().freeMemory();
            long totalMemory = Runtime.getRuntime().totalMemory();
            
            System.err.printf("Time = %.3f s\n", (endTime - startTime) / 1000.0);
            System.err.printf("Memory = %.3f MB\n", (totalMemory - freeMemory) / (float)(1 << 20));
            
            if (ret != 0)
                System.exit(ret);
            
        } catch (Throwable t) {
            t.printStackTrace(ONLINE_JUDGE ? System.out : System.err);
            System.exit(-1);
        }
    }
}