Vision has finally made it to Wakanda to get his MindStone extracted. The MindStone was linked to his brain in a highly sophisticated manner and Shuri had to solve a complex problem to extract the stone. The MindStone had $n$ integers inscribed in it and Shuri needs to apply the prefix sum operation on the array $k$ times to extract the stone.
Formally, given $n$ integers $A[1], A[2] ..... A[n]$ and a number $k$, apply the operation
$A[i] = \sum_{j=1}^{i} A[j]$
on the array $k$ times.
Finally Shuri needs to apply $modulo$ $(10^9 + 7)$ operation to each element of the array. Can you help Shuri accomplish this task before Thanos gets to them?

-----Input:-----
- First line of the input consists of two space separated integers $n$ and $k$. 
- Second line contains $n$ space separated integers $A[1] .. A[n]$.

-----Output:-----
In a single line print $n$ space separated integers, the values of the resultant array after applying all the operations.

-----Constraints-----
- $1 \leq n \leq 1000$
- $1 \leq k \leq 10^{12}$
- $1 \leq A[i] \leq 10^9$

-----Subtasks-----
- 20 Points: $1 \leq k \leq 1000$
- 30 Points: $1 \leq k \leq 1000000$
- 50 Points: Original Constraints

-----Sample Input:-----
$4$ $2$
$3$ $4$ $1$ $5$

-----Sample Output:-----
$3$ $10$ $18$ $31$

-----EXPLANATION:-----
After applying the prefix sum operation once the array becomes -> $3$ $7$ $8$ $13$
After applying the prefix sum operation for the second time, the array becomes -> $3$ $10$ $18$ $31$
After applying $modulo$ $(10^9 +7)$ operation, array becomes -> $3$ $10$ $18$ $31$

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

try:
    from itertools import accumulate
    n,k=map(int,input().strip().split())
    l=list(map(int,input().strip().split()))
    x=((10**9)+7)
    for i in range(0,k):
        l=list(accumulate(l))
    for i in l:
        print(i%x,end=" ")
except:
    pass

m=list(map(int,input().strip().split()))[:2]
n,k=m
lst=list(map(int,input().strip().split()))[:n]

h=0
while k!=0:
    sum=0
    for i in range(n):
        i=i+h

        sum+=lst[i]
        lst.append(sum)
    k-=1
    h+=n
M = 1000000007
# print(lst)
for j in range (len(lst)-n,len(lst)):
    
    print(lst[j]%M,end=" ")
    

# cook your dish here
from itertools import accumulate
N, K = map(int, input().split())
l= list(map(int, input().split()))
t= (10**9)+7
for i in range(K):
    l= list(accumulate(l))
for i in l:
    print(i%(t), end = ' ')

n,k1 = map(int, input().split())
arr  = list(map(int, input().split()))
for i in range(k1):
    for j in range(1,n):
        arr[j]=arr[j]+arr[j-1]
for k in range(len(arr)):
    print(arr[k]%1000000007,end=" ")



# cook your dish here
try:
    from itertools import accumulate
    n, k = map(int, input().split())
    lst = list(map(int, input().split()))
    temp = (10**9)+7
    for i in range(k):
        lst = list(accumulate(lst))
    for i in lst:
        print(i%(temp), end = ' ')
except EOFError as e:
    pass


#Vision and the MindStone
N,K = map(int,input().split())
data = list(map(int,input().split()))
output = []
output.append(data)
add = [data[0]]
for i in range(N-1):
    add.append(0)
for i in range(K):
    output.append(add)
for i in range(1,K+1):
    for j in range(1,N):
        output[i][j] = output[i-1][j] + output[i][j-1]
for i in output[K]:
    print(i%(10**9 + 7),end=" ")

# cook your dish here
from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

from itertools import *

try:
    x,y = map(int, input().split())
    l1=list (map(int,input().split()))


    for j in range (0,y):
        l1=list(accumulate(l1))

    for i in range(0,len(l1)):
        print(l1[i]%(pow(10,9)+7),end=' ')
except:
    pass


try:
    n,k=map(int,input().split()) 
    p=1000000007
    a=[int(x) for x in input().split()]
    b=a.copy()
    for i in range(k):
        for j in range(n):
            s=0
            for m in range(j+1):
                s+=a[m]
            b[j]=s
        a=b.copy()
    for o in range(n):
        b[o]=b[o]%p
        print(b[o],end=' ')
except:
    pass

from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')


from itertools import accumulate
n,k=map(int,input().strip().split())
l=list(map(int,input().strip().split()))
x=((10**9)+7)
for i in range(0,k):
    l=list(accumulate(l))
for i in l:
    print(i%x,end=" ")

# cook your dish here
try:
    from itertools import accumulate
    n,k=map(int,input().strip().split())
    l=list(map(int,input().strip().split()))
    x=((10**9)+7)
    for i in range(0,k):
        l=list(accumulate(l))
    for i in l:
        print(i%x,end=" ")
except:
    pass

# cook your dish here
# cook your dish here
list0=list(map(int,input().split()))
n=list0[0]
k=list0[1]
list1=list(map(int,input().split()))
M = 1000000007
for j in range(k):
    for i in range(n-1):
        list1[i+1]=((list1[i+1]%M)+(list1[i]%M))%M
for i in list1:
    print(i%M,end=" ")

# cook your dish here
from itertools import accumulate
list0=list(map(int,input().split()))
n=list0[0]
k=list0[1]
list1=list(map(int,input().split()))
M = 1000000007
for j in range(k):
    for i in range(n-1):
        list1[i+1]=list1[i+1]+list1[i]
for i in list1:
    print(i%M,end=" ")

from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

# cook your dish here
from itertools import accumulate
list0=list(map(int,input().split()))
n=list0[0]
k=list0[1]
list1=list(map(int,input().split()))
list2=list1[0:]
M = 1000000007
for j in range(k):
    list1=list(accumulate(list1))
for i in list1:
    print(i%M,end=" ")

from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

from itertools import accumulate
n1, k1 = map(int, input().split())
last = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k1):
    last = list(accumulate(last))
for i in last:
    print(i%(temp), end = ' ')

# cook your dish here
from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

# cook your dish here
list0=list(map(int,input().split()))
n=list0[0]
k=list0[1]
list1=list(map(int,input().split()))
M = 1000000007
for j in range(k):
    for i in range(n-1):
        list1[i+1]=list1[i+1]+list1[i]
for i in list1:
    print(i%M,end=" ")


from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

# cook your dish here
from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

# cook your dish here
from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')

from itertools import accumulate
n, k = map(int, input().split())
lst = list(map(int, input().split()))
temp = (10**9)+7
for i in range(k):
    lst = list(accumulate(lst))
for i in lst:
    print(i%(temp), end = ' ')