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

public class C {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    static final int MOD = 1000000007;

    int pow(int a, int b) {
        int res = 1;
        while (b > 0) {
            if ((b & 1) == 1)
                res = (int) ((long) res * a % MOD);
            a = (int)((long)a * a % MOD);
            b >>= 1;
        }
        return res;
    }

    void solve() throws IOException {
        int n = nextInt();
        int k = nextInt();

        int[] a = new int[n];

        for (int i = 0; i < n; i++)
            a[i] = nextInt();

        if (k == 0) {
            for (int i = 0; i < n; i++)
                out.print(a[i] + " ");
            out.println();
            return;
        }

        k--;

        int[] mult = new int[n];
        mult[0] = 1;
        for (int i = 1; i < n; i++)
            mult[i] = (int) ((long) mult[i - 1] * (k + i) % MOD * pow(i, MOD - 2) % MOD);

        int[] res = new int[n];
        for (int i = 0; i < n; i++)
            for (int j = 0; i + j < n; j++) {
                res[i + j] += (int)((long)a[i] * mult[j] % MOD);
                if (res[i + j] >= MOD)
                    res[i + j] -= MOD;
            }
        
        for (int i = 0; i < n; i++)
            out.print(res[i]  + " ");
    }

    void inp() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

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

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

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

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