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

# def find_cf(k,i,a):
#     cf=[1]
#     ans=0
#     for j in range(1,i):
#         aux= (i-j)/(k+i-j-1)*cf[-1]
#         cf.append(aux)
#         ans+=aux*a[j-1]
#     ans+=a[i-1]
#     return ans

mod= 10**9 + 7

def Combinations(n,k):
    return math.factorial(n)// (math.factorial(n-k)* math.factorial(k))


def partial_Sums(n, k, a):
    
    if(k==0): return a
    
    result=[a[0]]
    
    for i in range(2,n+1):
        # temp= find_cf(k,i,a)
        # result.append(temp)
        s_i=0
        for j in range(1,i+1):
            s_i+= Combinations(k+i-j-1, k-1)* a[j-1] % mod
        result.append(s_i)
    
    return result

a=[663, 360 ,509, 307, 311, 501, 523, 370, 302, 601, 541, 42, 328, 200, 196, 110, 573]
print(partial_Sums(17,239,a))


