Одновимірний клітинний автомат
Існує одномірний клітинний автомат, що складається з 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)
Кожен стан має бути представлений як ціле число, а числа мають бути розділені пробілом.