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.Locale;
import java.util.StringTokenizer;

public class PartialSums implements Runnable {
    static final long mod = 1000000007;
    void solve() throws IOException {
        int n = readInt();
        long k = readLong();
        long input[][] = new long[1][n];
        for(int i = 0 ; i < n; i ++) {
            input[0][i] = readLong();
        }
        long matrix[][] = new long[n][n];

        long ret[][] = input;
        if(k!=0)  {
            build(matrix, k);
            ret = multi(input, matrix);
        }
        for(int i = 0 ; i < n ; i ++) {
            if(i!=0)
                out.print(" ");
            out.print(ret[0][i]);
        }
        out.println();
    }

    long add(long a, long b) {
        return (a + b) % mod;
    }

    long multi(long a, long b) {
        return (a*b )%mod ;
    }

    void build(long matrix[][], long k) {
        matrix[0][0] = 1;
        BigInteger modB  = BigInteger.valueOf(mod);
        BigInteger value = BigInteger.valueOf(1);
        for(int i = 1; i < matrix.length ; i ++) {
            value = value.multiply(BigInteger.valueOf(k+i-1)).divide(BigInteger.valueOf(i));
            matrix[0][i] = value.mod(modB).longValue();
        }
        for(int i = 1; i < matrix.length; i ++)
            for(int j = i ; j < matrix.length ; j ++) {
                matrix[i][j] = matrix[i-1][j-1];
            }
    }

    long[][] multi(long[][] a, long[][] b) {
        long[][] ret = new long[a.length][b[0].length];

//        System.out.println(1);
        for(int i = 0 ; i < a.length; i ++)
            for(int j = 0; j < b[0].length; j ++) {
                long tmp = 0;
                for(int k = 0 ; k < b.length; k ++) {
                    tmp = add(tmp, multi(a[i][k], b[k][j]));
                }
                ret[i][j] = tmp;
            }

//        System.out.println(2);
        return ret;
    }

    long[][] power(long[][] a, long k){
        long[][] tmp = copy(a);
        long[][] ret = null;
        while(k!=0) {
            System.out.println(k);
            if(k%2==1) {
                if(ret == null)
                    ret = copy(tmp);
                else
                    ret = multi(ret, tmp);
            }
            k/=2;
            System.out.println(k+"..");
            tmp = multi(tmp, tmp);
        }
        return ret;
    }

    long[][] copy(long[][] a) {
        long[][] ret = new long[a.length][a[0].length];
       // System.out.println(1);
        for(int i = 0 ; i < a.length ; i ++)
            for(int j = 0; j < a[0].length; j ++)
                ret[i][j] = a[i][j];
       // System.out.println(2);
        return ret;
    }




    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new PartialSums().run();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            if (System.getProperty("ONLINE_JUDGE") != null) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("/Users/shenchen/input.txt"));
                out = new PrintWriter("/Users/shenchen/output.txt");
            }
            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }


}