Garbling Game#527
Pavel has invented a new game with an integer matrix. He takes an r \times c matrix with rows and columns, filling it with numbers from to from left to right and top to bottom ( in the upper-left corner, in the lower-right corner). He then begins to rearrange the numbers in the matrix according to the rules described below, writing down a sequence of numbers on a separate piece of paper. He calls this the garbling of the matrix.
The rearrangement rules are determined by a garbling map, which is an (r - 1) \times (c - 1) matrix of letters L, R, and N. An initial 4 \times 5 matrix and a sample 3 \times 4 garbling map are shown below.
Pavel garbles the matrix in a series of moves. On his first move, Pavel takes the number in the first row and first column (shown in parentheses above for clarity) and writes it down.
After writing the number, he performs a garbling move:
Pavel looks at the letter in the garbling map corresponding to the position of the number just written (on the first move, this is the letter in the upper-left corner). Depending on the letter in the garbling map, the 2 \times 2 block of the matrix whose upper-left corner contains the number just written (highlighted above) is rearranged as follows:
- R — the block is rotated clockwise. - L — the block is rotated counterclockwise. - N — Pavel does not change the matrix on this move.
On the second move, Pavel takes the number in the first row and second column, writes it down, and performs the garbling move, and so on. After c-1 moves, he finishes the first row and proceeds to the second row, continuing left to right and top to bottom. After (r-1)(c-1) moves, he has written down (r-1)(c-1) numbers and garbled the entire matrix, so he starts again from the upper-left corner, continuing to garble the matrix from left to right and top to bottom.
The matrices below show the effect of the first four moves using the sample garbling map.
The following sequence of numbers is written down in the first moves: . On the th move, the number from the second row and the first column is written, but the matrix remains unchanged, as the second row and the first column of the garbling map contains N. In six moves Pavel gets 1~7~7~9~1~8.
Given the garbling map and the number of moves Pavel makes in the game, determine how many times each number is written down by Pavel. Output the answer modulo 10^5.
The first line contains three integers , , and , where , (2 \leq r, c \leq 300) are the dimensions of the initial matrix, and (0 \leq n < 10^{100}) is the number of moves Pavel makes.
The following r-1 lines contain the garbling map, each with c-1 letters R, L, or N.
Output lines, each with one integer. The -th line should contain the number of times the number is written down by Pavel modulo 10^5 over moves.
Example 1