You are provided with an array \(A\) of size \(N\) that contains integers and two additional integers \(K\) and \(M\). You have defined the following functions:

\(M\) arrays are defined in such a way where the \(z^{th}\) of them is \(B_z=[A_0^z,A_1^z,...A_{N-1}^{z}], 1 \le z \le M\).
For an array \(X\), you define a series of \(K+1\) arrays \(F_0(X),F_1(X)...F_K(X)\), where:
- \(F_0(X)=X\)
- \(F_i(X)[q] = \sum_{j=0}^{q} F_{i-1}(X)[j] , \hspace{0.2cm} 1\le i \le K,0 \le q \le N-1\)

Note: This expression represents that the \(q^{th}\) element of \(F_i(X)\) is the prefix sum of the first \(q\) elements of \(F_{i-1}(X)\), where \(i \ge 1\).

Your task is to determine \(M\) integers, where the \(z^{th}\) integer is the \((N-1)^{th}\) element of \(F_K(B_z) , \hspace{0.2cm} 1 \le z \le M\).

As these numbers can be large, print them as modulo \(10^9+7\).

Input format

First line: Three space-separated integers \(N,\ M,\ and\ K\)
Second line: \(N\) space-separated integers where the \(i^{th}\) integer denotes \(A[i]\)

Output format

Print \(M\) space-separated integers, where the \(z^{th}\) integer denotes the \((N-1)^{th}\) element of \(F_k(B_z) , \hspace{0.2cm} 1 \le z \le M\). As these numbers can be large, you are required to print them as modulo \(10^9+7\).

Constraints

\(1 \le N , M , K \le 10^5\\ 1 \le A[i] < 10^9+7\)