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
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ull  unsigned long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
typedef  tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1000100;
vector < int > g[N];
int a[N], b[N], ans[N], t[N];
int t1, t2;
const int mod = 1e9 + 7;
int binpow(int x, int y){
    int res = 1;
    while(y){
        if (y % 2) res = res * x % mod;
        x = x * x % mod;
        y /= 2;
    }
    return res;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, k;
    cin >> n >> k;
    if (n > k){
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= k; i++){
            for (int j = 1; j <= n; j++)
                b[j] = (b[j - 1] + a[j]) % mod;
            for (int j = 1; j <= n; j++) a[j] = b[j];
        }
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
        return 0;
    }
    for (int i = 1; i <= n; i++) t[i] = binpow(i, mod - 2);
    for (int i = 1; i <= n; i++){
        b[i] = 1;
        for (int j = k + 1; j <= i + k - 1; j++)
            b[j] = b[j] * j % mod;
        for (int j = 1; j <= i - 1; j++)
            b[j] = b[j] * t[j] % mod;
    }
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        for (int j = 1; j <= i; j++)
            ans[i] = (ans[i] + b[i - j + 1] * a[j]) % mod;
        cout << ans[i] << " ";
    }
}
