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 C {
    static long mod = 1000000007;
    static long[] factInv;

    public static long[][] multiply(long[][] a, long[][] b) {
        long[][] c = new long[a.length][b[0].length];
        for (int i = 0; i < c.length; i++)
            for (int j = 0; j < c[0].length; j++)
                for (int k = 0; k < a.length; k++) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
                }
        return c;
    }

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        factInv = new long[2005];

        factInv[0] = 1;
        for (int i = 1; i < factInv.length; i++)
            factInv[i] = (factInv[i - 1] * i) % mod;
        for (int i = 1; i < factInv.length; i++)
            factInv[i] = modPow(factInv[i], mod - 2, mod);
        int n = in.nextInt();
        int k = in.nextInt();

        long[][] arr = new long[n][1];
        for (int i = 0; i < n; i++)
            arr[i][0] = in.nextInt();
        if (k == 0) {
            for (int i = 0; i < n; i++)
                System.out.print(arr[i][0] + " ");
            return;
        }
        long[] s = new long[n];
        for (int i = 0; i < n; i++)
            s[i] = S(k, i);
        long[][] mat = new long[n][n];
        for (int j = 0; j < mat.length; j++) {
            for (int i = 0; i < mat.length; i++) {
                int index = i - j;
                if (index >= 0)
                    mat[i][j] = s[index];
            }
        }
        arr = multiply(mat, arr);
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i][0] + " ");
    }

    public static long modPow(long a, long exp, long mod) {
        long res = 1 % mod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                res = (res * a) % mod;
            a = (a * a) % mod;
            exp >>= 1;
        }
        return res;
    }

    public static long C(int n, int k) {
        if (n - k < k)
            return C(n, n - k);
        long res = 1;
        for (long i = n; i >= n - k + 1; res %= mod, i--)
            res *= i;
        return (res * factInv[k]) % mod;
    }

    public static long S(int n, int r) {

        return C(n + r - 1, n - 1);
    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}
