There are $n$ children, numbered $1,2,\ldots,n$, sitting around a circle in a clockwise manner. The ${i}$th child has a piece of paper with the number $a_i$ written on it. They play the following game:

In the ${1}$st round, the child numbered ${i}$ increases his number by the sum of the numbers of his neighbors.  
In the $2$nd round, the child next in clockwise order increases his number by the sum of the numbers of his neighbors.
In the $3$rd round, the child next in clockwise order increases his number by the sum of the numbers of his neighbors.
And so on.  

The game ends after $m$ rounds have been played.  

For every ${i}$, find the numbers that the children end up with if the game starts with child ${i}$ playing the first round. Since the numbers can be large, output them modulo $10^9+7$.  

Input Format

The first line contains ${t}$, the number of test cases. ${t}$ cases follow.  

The first line of each test case contains two space-separated integers $n$ and $m$. The next line contains $n$ integers, the ${i}$th of which is $a_i$.  

Constraints

$1\leq t\leq15$  
$3\leq n\leq50$  
$1\leq m\leq10^9$  
$1\leq a_i\leq10^9$  

Output Format

For each test case, print $n$ lines, each having $n$ integers. The $j$th integer on the ${i}$th line contains the number that the $j$th child ends up with if the game starts with child ${i}$ playing the first round.  

Print a blank line after each test case except the last one.  

Since the numbers can be large, output them modulo $10^9+7$.  

Sample Input 0
2
5 1
10 20 30 40 50
3 4
1 2 1

Sample Output 0
80 20 30 40 50
10 60 30 40 50
10 20 90 40 50
10 20 30 120 50
10 20 30 40 100

23 7 12
11 21 6
7 13 24

Source: hackerrank | Difficulty: HARD
Tags: Matrices


Solutions:
from sys import stdin
from copy import deepcopy as dcop
from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations as cmb, takewhile, product, groupby as grpb
from itertools import repeat as rep
from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
lolPath = getcwd()
trace = 0
prof = 0
tst = 0
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)
filou = 'D:\\ZeDaddy\\Documents\\Hack\\Algebra\\Circle01.txt'
if home:
	print('home')
modo = 10 ** 9 + 7
if home:
	from mesures import ch

def rotg(v, r):
	ln = len(v)
	for ri in range(r, ln):
		yield v[ri]
	for ri in range(r):
		yield v[ri]

def rotd(v, r):
	ln = len(v)
	for ri in range(ln - r, ln):
		yield v[ri]
	for ri in range(ln - r):
		yield v[ri]

def sqmatmulmod(m1, m2, modo=None):
	if modo == None:
		return sqmatmul(m1, m2)
	mr = [[0] * len(m1)]
	for i in range(len(m1) - 1):
		mr += [mr[0].copy()]
	for l in range(len(m1)):
		for c in range(len(m1)):
			mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % modo
	return mr

def matUnit(n):
	r = []
	for ix in range(n):
		r = r + [[0] * ix + [1] + [0] * (n - ix - 1)]
	return r

def expMat(m1, po):
	r = matUnit(len(m1))
	em1 = m1.copy()
	bm = 1
	while po:
		if po & bm:
			r = sqmatmul(em1, r)
			po ^= bm
		em1 = sqmatmul(em1, em1)
		bm <<= 1
	return r

def expMatMod(m1, po, modo=None):
	r = matUnit(len(m1))
	em1 = m1.copy()
	bm = 1
	while po:
		if po & bm:
			r = sqmatmulmod(em1, r, modo)
			po ^= bm
		em1 = sqmatmulmod(em1, em1, modo)
		bm <<= 1
	return r

def matmulvec(m1, v, modo=None):
	if modo is None:
		return matmulvec_(m1, v)
	if len(v) != len(m1):
		print('erreur mul vect taille matrice et vecteur differents', len(v), len(m1))
		return None
	res = []
	for l in range(len(m1)):
		res += [sum((m1[l][ix] * v[ix] for ix in range(len(m1))))]
	return list((sum((m1[l][ix] * v[ix] for ix in range(len(m1)))) % modo for l in range(len(m1))))

def matmulvec_(m1, v):
	if type(v).__name__ == 'generator':
		v = list(v)
	return list((sum((m1[l][ix] * v[ix] for ix in range(len(m1)))) % modo for l in range(len(m1))))

def matprint(m1, txt=''):
	print('\n\n' + txt + '========>')
	lg = len(m1)
	lg = min(lg, 14)
	for l in m1[:lg]:
		for v in l[:lg]:
			print('{:9d},'.format(v), sep='', end=' ')
		print()

def prod(l):
	return reduce(lambda x, y: x * y % modo, l, 1)

def parMat(Nbs, M):
	ln = len(Nbs)
	mat = []
	for ix in range(1, ln):
		mat += [[0] * ix + [1] + [0] * (ln - (ix + 1))]
	mat += [[1, 1] + [0] * (ln - 3) + [1]]
	if trace & 4:
		print(mat)
	if trace & 4:
		matprint(mat, 'init')
	r = expMatMod(mat, M, modo)
	if trace & 4:
		matprint(r, 'exponentiee')
	r = list((list(rotd(matmulvec(r, rotg(Nbs, rv)), (M + rv) % ln)) for rv in range(ln)))
	return r
if home and filou:
	rd = open(filou, 'r')
else:
	rd = stdin
entree = rd.read(10000000)
Pars = entree.splitlines()
first = True
for ix in range(1, 2 * int(Pars[0].strip()) + 1, 2):
	if not first:
		print()
	first = False
	(N, M) = list((int(i.strip()) for i in Pars[ix].strip().split()))
	Nbs = list((int(i.strip()) for i in Pars[ix + 1].strip().split()))
	if home:
		cr = ch()
	r = parMat(Nbs, M)
	if home:
		print(cr.lap())
	for l in r:
		list((print(v, end=' ') for v in l))
		print()


import functools

def intmatvecmul(M, v, N, mod):
	out = []
	for i in range(N):
		acc = 0
		for j in range(N):
			acc = (acc + M[i][j] * v[j]) % mod
		out.append(acc)
	return out

def intmatmul(A, B, N, mod):
	out = []
	for i in range(N):
		row = []
		for j in range(N):
			acc = 0
			for k in range(N):
				acc = (acc + A[i][k] * B[k][j]) % mod
			row.append(acc)
		out.append(row)
	return out

def eye(N):
	out = []
	for i in range(N):
		row = []
		for j in range(N):
			if i == j:
				row.append(1)
			else:
				row.append(0)
		out.append(row)
	return out

def intmatpow(A, pwr, N, mod):
	tmp = A
	k = 1
	if pwr % 2 == 1:
		pwr -= 1
		acc = A
	else:
		acc = []
	while pwr > 0:
		tmp = intmatmul(tmp, tmp, N, mod)
		if pwr % 2 ** (k + 1) != 0:
			pwr -= 2 ** k
			if acc:
				acc = intmatmul(acc, tmp, N, mod)
			else:
				acc = tmp
		k += 1
	return acc
T = int(input())
for q in range(T):
	NM = [int(x) for x in input().split()]
	N = NM[0]
	M = NM[1]

	def nxt(i):
		if i == N - 1:
			return 0
		else:
			return i + 1

	def prev(i):
		if i == 0:
			return N - 1
		else:
			return i - 1
	stepmatrices = []
	for i in range(N):
		m = eye(N)
		m[i][prev(i)] = 1
		m[i][nxt(i)] = 1
		stepmatrices.append(m)
	Nstepmatrix = eye(N)
	for i in range(N):
		for j in range(N):
			Nstepmatrix[i][j] += Nstepmatrix[(i - 1) % N][j] + Nstepmatrix[(i + 1) % N][j]
	numbigsteps = M // N - 1
	numsmallsteps = M % N + N
	hugestepmatrix = intmatpow(Nstepmatrix, numbigsteps, N, 1000000007)
	ai = [int(x) for x in input().strip().split()]
	for x in range(N):
		state = ai.copy()
		if numbigsteps >= 1:
			for i in range(x, N):
				state[i] = (state[i] + state[prev(i)] + state[nxt(i)]) % 1000000007
			state = intmatvecmul(hugestepmatrix, state, N, 1000000007)
			for i in range(numsmallsteps - N + x):
				state[i % N] = (state[i % N] + state[(i - 1) % N] + state[(i + 1) % N]) % 1000000007
		else:
			count = 0
			i = x
			while count < M:
				state[i % N] = (state[i % N] + state[(i - 1) % N] + state[(i + 1) % N]) % 1000000007
				count += 1
				i = nxt(i)
		print(' '.join(map(str, state)))
	print()


import sys
from time import time

def mat_transpose(A):
	C = list()
	for c in range(len(A[0])):
		row = list()
		for r in range(len(A)):
			row.append(A[r][c])
		C.append(tuple(row))
	return tuple(C)

def mat_mul(A, B, m):
	if len(A[0]) != len(B):
		raise Exception('incompatible rows cols')
	(rows, cols) = (len(A), len(B[0]))
	C = list()
	for i in range(rows):
		row = list()
		for j in range(cols):
			sm = sum((A[i][k] * B[k][j] % m for k in range(len(B)))) % m
			row.append(sm)
		C.append(tuple(row))
	return tuple(C)

def mat_pow(A, p, m):
	if len(A[0]) != len(A):
		raise Exception('incompatible rows cols')
	C = list()
	for i in range(len(A)):
		row = [0] * len(A)
		row[i] = 1
		C.append(tuple(row))
	C = tuple(C)
	if p == 0:
		return C
	while p != 0:
		if p % 2 == 1:
			C = mat_mul(C, A, m)
		A = mat_mul(A, A, m)
		p //= 2
	return C

def round_gen(l):
	cache = list()
	for i in range(l):
		u = [0] * l
		u[i] = 1
		cache.append(u)
	while True:
		yield cache
		for i in range(l):
			iv = i
			iu = (iv - 1) % l
			iw = (iv + 1) % l
			(u, v, w) = (cache[i] for i in (iu, iv, iw))
			for i in range(l):
				v[i] += u[i] + w[i]

def str_arr(aa, delimeter=' '):
	return delimeter.join(map(str, aa))

def test(aa, r, m):

	def cache_str(cache):
		return '|'.join((' '.join(('% 4d' % v for v in u)) for u in cache))
	A = ((1, 2, 3), (3, 4, 5))
	B = ((1, 2, 3, 4), (3, 4, 5, 6), (7, 8, 9, 10))
	C = mat_mul(A, B, m)
	print('A=%s' % (A,), file=sys.stderr)
	print('AT=%s' % (mat_transpose(A),), file=sys.stderr)
	print('B=%s' % (B,), file=sys.stderr)
	print('C=%s' % (C,), file=sys.stderr)
	print('aa=%s' % (aa,), file=sys.stderr)
	for (i, uu) in enumerate(round_gen(len(aa)), 0):
		print('i=%d uu=%s' % (i, uu), file=sys.stderr)
		if i == r:
			break
	A = [[1, 1, 1], [1, 2, 2], [2, 3, 4]]
	for p in range(r + 1):
		print('p=%d uu=%s' % (p, mat_pow(A, p, m)), file=sys.stderr)
	return aa

def solve(aa, r, m):
	A = None
	for (i, cache) in enumerate(round_gen(len(aa))):
		if i == 1:
			A = cache
			break
	R = mat_transpose(mat_pow(A, r // len(aa), m))
	for index in range(len(aa)):
		V = [aa[index:] + aa[:index]]
		C = list(mat_mul(V, R, m)[0])
		for i in range(r % len(aa)):
			C[i] += C[(i - 1) % len(C)] + C[(i + 1) % len(C)]
			C[i] %= m
		S = C[-index:] + C[:-index]
		print(' '.join(map(str, S)))
	return aa
tm = time()
m = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	(_, r) = map(int, input().split())
	aa = tuple(map(int, input().split()))
	solve(aa, r, m)
	print()
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


import functools

def intmatvecmul(M, v, N, mod):
	out = []
	for i in range(N):
		acc = 0
		for j in range(N):
			acc = (acc + M[i][j] * v[j]) % mod
		out.append(acc)
	return out

def intmatmul(A, B, N, mod):
	out = []
	for i in range(N):
		row = []
		for j in range(N):
			acc = 0
			for k in range(N):
				acc = (acc + A[i][k] * B[k][j]) % mod
			row.append(acc)
		out.append(row)
	return out

def eye(N):
	out = []
	for i in range(N):
		row = []
		for j in range(N):
			if i == j:
				row.append(1)
			else:
				row.append(0)
		out.append(row)
	return out

def intmatpow(A, pwr, N, mod):
	tmp = A
	k = 1
	if pwr % 2 == 1:
		pwr -= 1
		acc = A
	else:
		acc = []
	while pwr > 0:
		tmp = intmatmul(tmp, tmp, N, mod)
		if pwr % 2 ** (k + 1) != 0:
			pwr -= 2 ** k
			if acc:
				acc = intmatmul(acc, tmp, N, mod)
			else:
				acc = tmp
		k += 1
	return acc
T = int(input())
for q in range(T):
	NM = [int(x) for x in input().split()]
	N = NM[0]
	M = NM[1]

	def nxt(i):
		if i == N - 1:
			return 0
		else:
			return i + 1

	def prev(i):
		if i == 0:
			return N - 1
		else:
			return i - 1
	stepmatrices = []
	for i in range(N):
		m = eye(N)
		m[i][prev(i)] = 1
		m[i][nxt(i)] = 1
		stepmatrices.append(m)
	Nstepmatrix = eye(N)
	for i in range(N):
		for j in range(N):
			Nstepmatrix[i][j] += Nstepmatrix[(i - 1) % N][j] + Nstepmatrix[(i + 1) % N][j]
	numbigsteps = M // N - 1
	numsmallsteps = M % N + N
	hugestepmatrix = intmatpow(Nstepmatrix, numbigsteps, N, 1000000007)
	ai = [int(x) for x in input().strip().split()]
	for x in range(N):
		state = ai.copy()
		if numbigsteps >= 1:
			for i in range(x, N):
				state[i] = (state[i] + state[prev(i)] + state[nxt(i)]) % 1000000007
			state = intmatvecmul(hugestepmatrix, state, N, 1000000007)
			for i in range(numsmallsteps - N + x):
				state[i % N] = (state[i % N] + state[(i - 1) % N] + state[(i + 1) % N]) % 1000000007
		else:
			count = 0
			i = x
			while count < M:
				state[i % N] = (state[i % N] + state[(i - 1) % N] + state[(i + 1) % N]) % 1000000007
				count += 1
				i = nxt(i)
		print(' '.join(map(str, state)))
	print()


def productList(L):
	X = L[0].copy()
	for i in range(1, len(L)):
		X = productMatrix(X, L[i])
	return X

def productMatrix(A, B):
	BB = transpose(B)
	return [[sum([x * y for (x, y) in zip(A[i], BB[j])]) for j in range(len(B[0]))] for i in range(len(A))]

def transpose(X):
	return [[X[i][j] for i in range(len(X))] for j in range(len(X[0]))]

def productMatrixVector(X, a, mod):
	return [sum([x * y for (x, y) in zip(X[i], a)]) % mod for i in range(len(X))]

def createMatList(n, k):
	kk = k - 1
	L = []
	S = []
	for j in range(n):
		X = [[0 for _ in range(n)] for _ in range(n)]
		Y = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			X[i][i] = 1
			Y[i][i] = 1
			if i == kk:
				X[i][(i - 1) % n] = 1
				X[i][(i + 1) % n] = 1
				Y[i][(i - 1) % n] = -1
				Y[i][(i + 1) % n] = -1
		L.append(X)
		S.append(Y)
		kk = (kk + 1) % n
	return (L, S)

def modMatrix(X, m):
	return [[c % m for c in l] for l in X]

def fastMatExp(X, e, m):
	result = [[1 if i == j else 0 for i in range(len(X))] for j in range(len(X))]
	while e > 0:
		if e & 1 > 0:
			result = modMatrix(productMatrix(result, X), m)
		e >>= 1
		X = modMatrix(productMatrix(X, X), m)
	return result

def createGenMatrix(n, q):
	result = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
	result2 = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
	result[0][1] = result[0][-1] = 1
	if q > 0:
		result2[0][1] = result2[0][-1] = 1
	for i in range(1, n - 1):
		result[i] = result[i - 1].copy()
		result[i][i] += 1
		result[i][i + 1] += 1
		if i < q:
			result2[i] = result2[i - 1].copy()
			result2[i][i] += 1
			result2[i][i + 1] += 1
	result[-1] = result[-2].copy()
	result[-1][0] = 2
	result[-1][1] = 3
	result[-1][-1] = 4
	return (result, result2)
mod = 1000000007
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	(L, S) = createMatList(n, 1)
	(P, R) = createGenMatrix(n, m % n)
	X = fastMatExp(P, m // n, mod)
	X = productMatrix(R, X)
	q = m % n
	for i in range(1, n + 1):
		A = a.copy()
		for j in range(i - 1, 0, -1):
			A = productMatrixVector(S[j - 1], A, mod)
		A = productMatrixVector(X, A, mod)
		for j in range(1, i):
			A = productMatrixVector(L[(j - 1 + q) % n], A, mod)
		print(*A)
	if _ < t - 1:
		print('')


import os, sys

def power_peasant_3(a, n, mult3, unity):
	adim = len(a)
	prod = unity
	tmp = [[0] * adim for _ in range(adim)]
	pwr = a
	while n != 0:
		if n % 2 != 0:
			mult3(tmp, prod, pwr)
			(tmp, prod) = (prod, tmp)
		n >>= 1
		if n == 0:
			break
		mult3(tmp, pwr, pwr)
		(tmp, pwr) = (pwr, tmp)
	return prod

def matrix_unit(n):
	return [[1 if col == row else 0 for col in range(n)] for row in range(n)]

def matrix_mod_product_3(m, dest, A, B):
	n = len(dest)
	for row in range(n):
		for col in range(n):
			(s, arow) = (0, A[row])
			for i in range(n):
				s += arow[i] * B[i][col]
			dest[row][col] = s % m

def matrix_mod_apply(m, A, v):
	n = len(A)
	res = [0] * n
	for row in range(n):
		(s, arow) = (0, A[row])
		for i in range(n):
			s += arow[i] * v[i]
		res[row] = s % m
	return res
MOD = 10 ** 9 + 7

def circle_map(a, n, k):
	a[k] = (a[k] + a[(k - 1) % n] + a[(k + 1) % n]) % MOD

def circle_sum(a, m):
	n = len(a)
	A = []
	for k in range(n):
		if k == 0:
			row = [0] * n
			row[n - 1] = row[0] = row[1] = 1
		elif k == n - 1:
			row = A[k - 1].copy()
			for i in range(n):
				row[i] += A[0][i]
			row[k] += 1
		else:
			row = A[k - 1].copy()
			row[k] += 1
			row[(k + 1) % n] += 1
		A.append(row)
	mn = m // n
	if mn >= 3:
		mn -= 2
		mn2 = mn * n
		unity = matrix_unit(n)

		def mult3(dst, A, B):
			return matrix_mod_product_3(MOD, dst, A, B)
		Ap = power_peasant_3(A, mn, mult3, unity)
	else:
		mn = 0
	res = []
	for i in range(n):
		b = a.copy()
		k = 0
		for _ in range(min(m, n - i)):
			circle_map(b, n, (i + k) % n)
			k += 1
		if mn >= 1:
			b = matrix_mod_apply(MOD, Ap, b)
			k += mn2
		r2 = m - k
		assert r2 >= 0
		for _ in range(r2):
			circle_map(b, n, (i + k) % n)
			k += 1
		res.append(b)
	if False and m % n == 0:
		unity = matrix_unit(n)

		def mult3(dst, A, B):
			return matrix_mod_product_3(MOD, dst, A, B)
		Am = power_peasant_3(A, m // n, mult3, unity)
		print('** TEST: row0', m // n, matrix_mod_apply(MOD, Am, a))
	for row in res:
		print(' '.join(map(str, row)))

def main():
	ncases = int(sys.stdin.readline())
	for ti in range(ncases):
		(n, m) = list(map(int, sys.stdin.readline().split()))
		a = list(map(int, sys.stdin.readline().split()))
		if ti > 0:
			print()
		circle_sum(a, m)
main()


modulo_constant = 10 ** 9 + 7

def mx_times(a, b, mo):
	return [[sum((a * b for (a, b) in zip(a_row, b_col))) % mo for b_col in zip(*b)] for a_row in a]

def mx_unit(rank):
	return [[0] * i + [1] + (rank - i - 1) * [0] for i in range(rank)]

def mx_pow(mx, n, mo):
	rank = len(mx)
	ret = mx_unit(rank)
	while n:
		if n & 1:
			ret = mx_times(ret, mx, mo)
		n >>= 1
		mx = mx_times(mx, mx, mo)
	return ret

def mx_step(n, i):
	ret = mx_unit(n)
	ret[(i + 1) % n][i] = ret[(i - 1) % n][i] = 1
	return ret

def circle_summation(steps, vec):
	n = len(vec)
	init = [vec[-i:] + vec[:-i] for i in range(n, 0, -1)]
	if steps >= n:
		full = mx_unit(n)
		for i in range(n):
			full = mx_times(full, mx_step(n, i), modulo_constant)
		init = mx_times(init, mx_pow(full, steps // n, modulo_constant), modulo_constant)
		steps = steps % n
	for i in range(steps):
		init = mx_times(init, mx_step(n, i), modulo_constant)
	return [row[-i:] + row[:-i] for (i, row) in enumerate(init)]

def run_circle_summation(reader=input, printer=print):
	t = int(reader())
	for _ in range(t):
		(n, m) = [int(x) for x in reader().split()]
		vec = [int(x) for x in reader().split()]
		assert n == len(vec)
		for row in circle_summation(m, vec):
			printer(' '.join(map(str, row)))
		printer('')
run_circle_summation()


mod = 1000000007

def matpow(a, n, x):
	toret = []
	for i in range(n):
		row = [0] * n
		row[i] = 1
		toret.append(row)
	apow2 = a
	curr = x
	while curr > 0:
		if curr % 2 == 1:
			nextret = []
			for i in range(n):
				row = [0] * n
				for j in range(n):
					for k in range(n):
						row[j] = (row[j] + toret[i][k] * apow2[k][j]) % mod
				nextret.append(row)
			toret = nextret
		nextapow = []
		for i in range(n):
			row = [0] * n
			for j in range(n):
				for k in range(n):
					row[j] = (row[j] + apow2[i][k] * apow2[k][j]) % mod
			nextapow.append(row)
		apow2 = nextapow
		curr //= 2
	return toret
t = int(input())
for _ in range(t):
	[n, m] = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	stepmat = []
	for i in range(n):
		steprow = [0] * n
		steprow[(i + 1) % n] = 1
		stepmat.append(steprow)
	stepmat[0][0] = 1
	stepmat[0][2] = 1
	steppow = matpow(stepmat, n, m)
	for i in range(n):
		for j in range(n):
			toput = 0
			for k in range(n):
				toput = (toput + steppow[(j - i - m + 1) % n][(k - i + 1) % n] * a[k]) % mod
			print(toput, end=' ')
		print()
	print()


MOD = 1000000007

def mult(a, b):
	n = len(a)
	c = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(n):
			for k in range(n):
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD
	return c

def exp(m, e):
	res = [[1 if i == j else 0 for j in range(len(m))] for i in range(len(m))]
	while e > 0:
		if e & 1:
			res = mult(res, m)
		m = mult(m, m)
		e >>= 1
	return res

def get_matrix(n, m):
	mat = [[0 for i in range(n)] for j in range(n)]
	for i in range(1, n):
		mat[i - 1][i] = 1
	mat[n - 1][0] = mat[n - 1][1] = mat[n - 1][n - 1] = 1
	return exp(mat, m)

def mult_vec(mat, vec):
	n = len(mat)
	res = [0 for i in range(n)]
	for i in range(n):
		for j in range(n):
			res[i] = (res[i] + mat[i][j] * vec[j]) % MOD
	return res
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	M = get_matrix(n, m)
	r = m % n
	for i in range(n):
		res = mult_vec(M, a)
		print(*res[-r:] + res[:-r])
		r = (r + 1) % n
		a = a[1:] + a[:1]
	if _ < t - 1:
		print()