Одномерный клеточный автомат
Одномерный клеточный автомат состоит из N ячеек, пронумерованных от 0 до N-1.
Каждая ячейка имеет состояние, выраженное неотрицательным целым числом, меньшим M. Состояния ячеек изменяются с течением времени на дискретных временных шагах. Обозначим состояние i-й ячейки в момент времени t как S(i, t). Состояние в момент времени t+1 определяется следующим уравнением:
S(i, t+1) = (A × S(i-1, t) + B × S(i, t) + C × S(i+1, t)) mod M, (1)
где A, B и C — неотрицательные целые константы. Для i < 0 или N ≤ i определяем S(i, t) = 0.
Зная определение автомата и начальные состояния ячеек, ваша задача — написать программу, которая вычисляет состояния ячеек в заданный момент времени T.
Входные данные
Входные данные состоят из нескольких наборов данных. Каждый набор данных имеет следующий формат:
N M A B C T
S(0, 0) S(1, 0) ... S(N-1, 0)
Первая строка набора данных содержит шесть целых чисел: N, M, A, B, C и T. Здесь N — количество ячеек, M — модуль в уравнении (1), A, B и C — коэффициенты в уравнении (1), а T — момент времени, для которого нужно вычислить состояния.
Вы можете предположить, что 0 < N ≤ 50, 0 < M ≤ 1000, 0 ≤ A, B, C < M и 0 ≤ T ≤ 10^9.
Вторая строка содержит N целых чисел, каждое из которых неотрицательно и меньше M. Эти числа представляют состояния ячеек в момент времени ноль.
Строка, содержащая шесть нулей, указывает на конец ввода.
Выходные данные
Для каждого набора данных выведите строку, содержащую состояния ячеек в момент времени T. Формат вывода следующий:
S(0, T) S(1, T) ... S(N-1, T)
Каждое состояние должно быть представлено как целое число, и числа должны быть разделены пробелом.