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>).


def poo(a,e,mod):
  if e==0:
    return 1
  if e==1:
    return a%mod
  ans=poo(a,e//2)
  ans*=ans
  ans%=mod
  if e%2==1:
    ans*=a
  ans%=mod
  return ans

def partial_sum(N,M,arr):
  matrix=[[0 for i in range(2000)] for j in range(2000)]
  mod=10**9+7
  if M==0:
    return arr

  matrix[0][0]=1
  for i in range(1,N):
    matrix[i][0]=matrix[i-1][0]
    matrix[i][0]*=(M+i-1)%mod
    matrix[i][0]%=mod
    if i!=1:
      matrix[i][0]*=pow(i,mod-2,mod)
    matrix[i][0]%=mod

  diff=0
  for col  in range(1,N):
    diff+=1
    for i in range(diff):
      matrix[i][col]=0
    for i in range(diff,N):
      matrix[i][col]=matrix[i-1][col-1]
    
  ans=[]
  for i in range(N):
    an=0
    for j in range(N):
      an+=matrix[i][j]*arr[j]
      an%=mod
    ans.append((an+mod)%mod)
  return ans


N,M=map(int,input().split())
arr=list(map(int,input().split()))
print(partial_sum(N,M,arr))