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.InputStreamReader;
import java.io.IOException;
import java.math.BigDecimal;
import java.util.Locale;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author aircube
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastInputReader in = new FastInputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
    final int MOD = 1000000000 + 7;
	public void solve(int testNumber, FastInputReader in, PrintWriter out) {
        int n = in.nextInt();
        int k = in.nextInt();
        int[] r = new int[n];
        InputUtils.inputArray(in, r);
        int[] v = build(n, k);
        int[][] mat = build(v);
        int[] res = mul(r, mat);
        OutputUtils.outArray(out, res);

//        int[][]a=new int[n][n];
//        for (int i = 0; i < n; ++i) {
//            for (int j = 0; j <= i; ++j)
//                a[i][j] = 1;
//        }
//
//        int[][]b=clone(a);
//        for (int it = 0; it < 100; ++it) {
//            out.println("iter = " + (it + 1));
//            a = MatrixUtils.mul(a, b, 1000000000 + 7);
//            for (int i = 0; i < n; ++i) {
//                for (int j = 0; j < n; ++j)
//                    out.print(a[i][j]  + " ");
//                out.println();
//            }
//            int[][]mat1 = build(build(n, it + 2));
//            out.println();
//            for (int i = 0; i < mat.length; ++i) {
//                out.println(Arrays.toString(mat1[i]));
//            }
//            out.println("---------------------------------------");
//        }
	}

    private int[][] build(int[] v) {
        int n = v.length;
        int[][]mat=new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                mat[j][i] = v[j - i];
            }
        }
        return mat;
    }

    private int[] mul(int[] r, int[][] mat) {
        int[] ans = new int[r.length];
        for (int i = 0; i < ans.length; ++i) {
            long res = 0;
            for (int j = 0; j < ans.length; ++j) {
                res = (res + (long)mat[i][j] * r[j] % MOD) % MOD;
            }
            ans[i] = (int) res;
        }
        return ans;
    }

    private int[] build(int n, int k) {
        int[]a=new int[n];
        BigInteger cur = BigInteger.valueOf(1);
        for (int i = 0; i < n; ++i) {
            if (i == 0) {
                a[i] = cur.intValue();
            } else {
                BigInteger tmp =cnk (k - 1 + i, k - 1, cur);
                a[i] = tmp.mod(BigInteger.valueOf(MOD)).intValue();
                cur = tmp;
            }
        }
        return a;
    }

    private BigInteger cnk(int n, int k, BigInteger prev) {
        BigInteger now = prev.multiply(BigInteger.valueOf(n));
        now = now.divide(BigInteger.valueOf(n - k));

        return now;
    }

    }

class FastInputReader {
    private StringTokenizer tokenizer;
    public BufferedReader reader;

    public FastInputReader(InputStream inputStream) {
        reader = new BufferedReader(new InputStreamReader(inputStream));
        tokenizer = null;
    }

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

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

    }

class InputUtils {
    public static void inputArray(FastInputReader in, int[]... arrays) {
        for (int i = 0; i < arrays[0].length; ++i) {
            for (int j = 0; j < arrays.length; ++j) {
                arrays[j][i] = in.nextInt();
            }
        }
    }

    }

class OutputUtils {
    public static void outArray(PrintWriter out, int[] array) {
        outArray(out, array, true);
    }

    public static void outArray(PrintWriter out, int[] array, boolean endLine) {
        boolean first = true;
        for (int x : array) {
            if (!first)
                out.print(' ');
            first = false;
            out.print(x);
        }
        if (endLine)
            out.println();
    }


    }

