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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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
for j in range(len(lst) - n, len(lst)):
	print(lst[j] % M, end=' ')


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=' ')


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


(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=' ')


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


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=' ')


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
(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=' ')