There is a one-dimensional cellular automaton consisting of N cells. Cells are numbered from 0 to N − 1.

Each cell has a state represented as a non-negative integer less than M. The states of cells evolve through discrete time steps. We denote the state of the i-th cell at time t as S(i, t). The state at time t + 1 is defined by the equation

S(i, t + 1) = (A × S(i − 1, t) + B × S(i, t) + C × S(i + 1, t)) mod M,         (1)

where A, B and C are non-negative integer constants. For i < 0 or N ≤ i, we define S(i, t) = 0.

Given an automaton definition and initial states of cells, your mission is to write a program that computes the states of the cells at a specified time T.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.

N M A B C T
S(0, 0) S(1, 0) ... S(N − 1, 0)


The first line of a dataset consists of six integers, namely N, M, A, B, C and T. N is the number of cells. M is the modulus in the equation (1). A, B and C are coefficients in the equation (1). Finally, T is the time for which you should compute the states.

You may assume that 0 < N ≤ 50, 0 < M ≤ 1000, 0 ≤ A, B, C < M and 0 ≤ T ≤ 109.

The second line consists of N integers, each of which is non-negative and less than M. They represent the states of the cells at time zero.

A line containing six zeros indicates the end of the input.

Output

For each dataset, output a line that contains the states of the cells at time T. The format of the output is as follows.

S(0, T) S(1, T) ... S(N − 1, T)

Each state must be represented as an integer and the integers must be separated by a space.

Example

Input

5 4 1 3 2 0
0 1 2 0 1
5 7 1 3 2 1
0 1 2 0 1
5 13 1 3 2 11
0 1 2 0 1
5 5 2 0 1 100
0 1 2 0 1
6 6 0 2 3 1000
0 1 2 0 1 4
20 1000 0 2 3 1000000000
0 1 2 0 1 0 1 2 0 1 0 1 2 0 1 0 1 2 0 1
30 2 1 0 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
30 2 1 1 1 1000000000
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
30 5 2 3 1 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0


Output

0 1 2 0 1
2 0 0 4 3
2 12 10 9 11
3 0 4 2 1
0 4 2 0 4 4
0 376 752 0 376 0 376 752 0 376 0 376 752 0 376 0 376 752 0 376
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 3 2 2 2 3 3 1 4 3 1 2 3 0 4 3 3 0 4 2 2 2 2 1 1 2 1 3 0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from operator import mul

def dot(v1, v2):
	return sum(map(mul, v1, v2))

def mat_mul(A, B, m):
	tB = tuple(zip(*B))
	return [[dot(A_i, B_j) % m for B_j in tB] for A_i in A]

def mat_pow(X, n, m):
	s = len(X)
	A = [[0] * s for i in range(s)]
	for i in range(s):
		A[i][i] = 1
	while n > 0:
		if n & 1:
			A = mat_mul(A, X, m)
		X = mat_mul(X, X, m)
		n >>= 1
	return A

def solve():
	from sys import stdin
	file_input = stdin
	while True:
		(N, M, A, B, C, T) = map(int, file_input.readline().split())
		if N == 0:
			break
		s = [list(map(int, file_input.readline().split()))]
		X = [[0] * N for i in range(N)]
		X[0][0] = B
		X[0][1] = A
		for (i, X_i) in enumerate(X[1:N - 1], start=1):
			X_i[i - 1] = C
			X_i[i] = B
			X_i[i + 1] = A
		X[-1][-2] = C
		X[-1][-1] = B
		ans = mat_mul(s, mat_pow(X, T, M), M)
		print(*ans[0])
solve()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(0, -1), (1, 0), (0, 1), (-1, 0)]
ddn = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, -1), (-1, 0), (-1, 1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	rr = []
	while True:
		(n, M, A, B, C, T) = LI()
		if n == 0:
			break
		a = tuple(LI())
		if T == 0:
			rr.append(' '.join(map(str, a)))
			continue
		m = [[0] * n for _ in range(n)]
		for i in range(n):
			m[i][i] = B
			if i > 0:
				m[i][i - 1] = A
			if i < n - 1:
				m[i][i + 1] = C
		mod = M

		class Matrix:

			def __init__(self, A):
				self.A = A
				self.row = len(A)
				self.col = len(A[0])

			def __iter__(self):
				return self.A.__iter__()

			def __getitem__(self, i):
				return self.A.__getitem__(i)

			def __add__(self, B):
				aa = self.A
				bb = B.A
				return Matrix([[aa[i][j] + bb[i][j] for j in range(self.col)] for i in range(self.row)])

			def __sub__(self, B):
				aa = self.A
				bb = B.A
				return Matrix([[aa[i][j] - bb[i][j] for j in range(self.col)] for i in range(self.row)])

			def __mul__(self, B):
				bb = [[B.A[j][i] for j in range(B.row)] for i in range(B.col)]
				return Matrix([[sum([ak * bk for (ak, bk) in zip(ai, bj)]) % mod for bj in bb] for ai in self.A])

			def __truediv__(self, x):
				pass

			def pow(self, n):
				A = self
				r = Matrix([[0 if j != i else 1 for j in range(self.row)] for i in range(self.row)])
				while n > 0:
					if n % 2 == 1:
						r *= A
					A *= A
					n //= 2
				return r

			def __str__(self):
				return self.A.__str__()
		m = Matrix(m)
		mp = m.pow(T)
		r = mp * Matrix([[a[i]] for i in range(n)])
		rr.append(' '.join(map(lambda x: str(x[0]), r)))
	return '\n'.join(map(str, rr))
print(main())


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LS()
	return l
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	s = S()
	n = len(s)
	d = [-1 for i in range(n)]
	k = 0
	m = 0
	for i in range(n):
		if s[i] == '[':
			k += 1
		elif s[i] == ']':
			k -= 1
		elif s[i] == '-':
			d[i] = k
		else:
			m += 1
	depth = max(d)
	f = defaultdict(int)
	for i in range(m):
		(a, b) = input().split()
		f[a] = int(b)
	for i in range(1, depth + 1)[::-1]:
		j = 0
		while j < len(s):
			if d[j] == i:
				if f[s[j - 1]] == 0:
					if f[s[j + 1]] == 0:
						print('No')
						quit()
					else:
						w = s[j + 1]
				elif f[s[j + 1]] != 0:
					print('No')
					quit()
				else:
					w = s[j - 1]
				f[w] -= 1
				d = d[:j - 2] + [None] + d[j + 3:]
				s = s[:j - 2] + [w] + s[j + 3:]
				j -= 2
			j += 1
	if f[s[0]] == 0:
		print('Yes')
	else:
		print('No')
	return

def B():
	(n, k) = LI()
	s = S()
	t = S()
	q = deque()
	ans = 0
	for i in range(n):
		if s[i] == 'B' and t[i] == 'W':
			if q:
				x = q.popleft()
				if i - x >= k:
					ans += 1
					while q:
						q.popleft()
			q.append(i)
	if q:
		ans += 1
	for i in range(n):
		if s[i] == 'W' and t[i] == 'B':
			if q:
				x = q.popleft()
				if i - x >= k:
					ans += 1
					while q:
						q.popleft()
			q.append(i)
	if q:
		ans += 1
	print(ans)
	return

def C():
	n = I()
	s = SR(n)
	t = S()
	return
from operator import mul

def D():

	def dot(a, b):
		return sum(map(mul, a, b))

	def mul_matrix(a, b, m):
		tb = tuple(zip(*b))
		return [[dot(a_i, b_j) % m for b_j in tb] for a_i in a]

	def pow_matrix(a, n, m):
		h = len(a)
		b = [[1 if i == j else 0 for j in range(h)] for i in range(h)]
		k = n
		while k:
			if k & 1:
				b = mul_matrix(b, a, m)
			a = mul_matrix(a, a, m)
			k >>= 1
		return b
	while 1:
		(n, m, a, b, c, t) = LI()
		if n == 0:
			break
		s = LI()
		s2 = [[s[i] for j in range(1)] for i in range(n)]
		mat = [[0 for j in range(n)] for i in range(n)]
		mat[0][0] = b
		mat[0][1] = c
		for i in range(1, n - 1):
			mat[i][i - 1] = a
			mat[i][i] = b
			mat[i][i + 1] = c
		mat[n - 1][-2] = a
		mat[n - 1][-1] = b
		mat = pow_matrix(mat, t, m)
		mat = mul_matrix(mat, s2, m)
		for i in mat[:-1]:
			print(i[0], end=' ')
		print(mat[-1][0])
	return

def E():

	def surface(x, y, z):
		return ((x == 0) | (x == a - 1)) + ((y == 0) | (y == b - 1)) + ((z == 0) | (z == c - 1)) + k
	d = [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1)]
	(a, b, c, n) = LI()
	s = [0 for i in range(7)]
	k = (a == 1) + (b == 1) + (c == 1)
	if k == 0:
		s[1] = 2 * (max(0, a - 2) * max(0, b - 2) + max(0, c - 2) * max(0, b - 2) + max(0, a - 2) * max(0, c - 2))
		s[2] = 4 * (max(0, a - 2) + max(0, b - 2) + max(0, c - 2))
		s[3] = 8
	elif k == 1:
		s[2] = max(0, a - 2) * max(0, b - 2) + max(0, c - 2) * max(0, b - 2) + max(0, a - 2) * max(0, c - 2)
		s[3] = 2 * (max(0, a - 2) + max(0, b - 2) + max(0, c - 2))
		s[4] = 4
	elif k == 2:
		s[4] = max(0, a - 2) + max(0, b - 2) + max(0, c - 2)
		s[5] = 2
	else:
		s[6] = 1
	f = defaultdict(int)
	for i in range(n):
		(x, y, z) = LI()
		s[surface(x, y, z)] -= 1
		f[x, y, z] = -1
		for (dx, dy, dz) in d:
			if f[x + dx, y + dy, z + dz] != -1:
				f[x + dx, y + dy, z + dz] += 1
	ans = 0
	for (i, j) in f.items():
		if j != -1:
			(x, y, z) = i
			if 0 <= x < a and 0 <= y < b and (0 <= z < c):
				ans += j + surface(x, y, z)
				s[surface(x, y, z)] -= 1
	for i in range(1, 7):
		ans += i * s[i]
	print(ans)
	return

def F():
	return

def G():
	return

def H():
	return

def I_():
	return

def J():
	return
D()