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$