One-Dimensional Cellular Automaton#5414
There is a one-dimensional cellular automaton consisting of cells. Cells are numbered from to N-1.
Each cell has a state represented as a non-negative integer less than . The states of cells evolve through discrete time steps. We denote the state of the -th cell at time as S(i, t). The state at time t+1 is defined by the equation
where , and are non-negative integer constants. For i < 0 or N \le 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 .
The input is a sequence of datasets. Each dataset is formatted as follows.
S(0, 0) S(1, 0) S(N-1, 0)
The first line of a dataset consists of six integers, namely , , , , and . is the number of cells. is the modulus in the equation (1). , and are coefficients in the equation (1). Finally, is the time for which you should compute the states.
You may assume that 0 < N \le 50, 0 < M \le 1000, 0 \le A, B, C < M and 0 \le T \le 10^9.
The second line consists of integers, each of which is non-negative and less than . They represent the states of the cells at time zero.
A line containing six zeros indicates the end of the input.
For each dataset, output a line that contains the states of the cells at time . 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 1