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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/cdc22b6f0de971f5a4a64b6f9e22d76a719ec5b7.png" style="max-width: 100.0%;max-height: 100.0%;"/>. The operation *x* *mod* *y* means that we take the remainder of the division of number *x* by number *y*. 1.  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* (*a*<sub class="lower-index">*i*</sub> = *s*<sub class="lower-index">*i*</sub>). 
You task is to find array *a* after exactly *k* described operations are applied.
The first line contains two space-separated integers *n* and *k* (1 ≤ *n* ≤ 2000, 0 ≤ *k* ≤ 10<sup class="upper-index">9</sup>). The next line contains *n* space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> — elements of the array *a* (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1e6;
const int MOD = 1e9 + 7;

ll fac[MAXN + 1];
ll inv[MAXN + 1];

ll exp(ll x, ll y, ll p) {
	ll res = 1; x %= p;
	while (y) {
		if (y & 1) {
			res *= x; res %= p; 
		}
		x *= x;
		x %= p;
		y >>= 1;
	}
	return res;
}

void factorial() {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) {
		fac[i] = fac[i - 1] * i % MOD;
	}
}

void inverses() {
	inv[0] = 1;
	for (int i = 1; i <= MAXN; i++) {
		inv[i] = exp(fac[i], MOD - 2, MOD);
	}
}

ll choose(int n, int r) {
	return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
}

int main() {
    factorial();
	inverses();
    int n, m;
    cin >> n >> m;
    vector<int> a(n), res(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> coefficients {1, m};
    for (int i = 2; i < n; ++i)
        coefficients.push_back(choose(m + i - 1, i));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i; ++j)
            res[i] += (a[j] * coefficients[i - j]), res[i] %= MOD;
    for (int i = 0; i < n; ++i) 
        cout << res[i] << " \n"[i == n - 1];
}

