뒤섞기 게임

파벨은 정수 행렬 위에서 하는 새로운 게임을 만들었다. 먼저 $r$개의 행과 $c$개의 열을 가진 $r \times c$ 행렬을 준비하고, $1$부터 $rc$까지의 수를 왼쪽에서 오른쪽으로, 위에서 아래로 채운다. 즉 $1$은 왼쪽 위 구석에, $rc$는 오른쪽 아래 구석에 놓인다. 따라서 $i$행 $j$열(둘 다 $1$부터 시작)의 칸에는 처음에 값 $(i-1)\cdot c + j$가 들어 있다.

파벨은 아래 규칙에 따라 행렬을 반복해서 뒤섞으면서, 별도의 종이에 수의 수열을 적어 나간다. 그는 이것을 행렬의 뒤섞기라고 부른다. 뒤섞는 방법은 뒤섞기 지도로 정해진다. 뒤섞기 지도는 각 칸이 문자 L, R, N 중 하나인 $(r-1) \times (c-1)$ 행렬이다.

파벨은 여러 번의 차례에 걸쳐 게임을 진행한다. 각 차례는 $2 \times 2$ 블록의 왼쪽 위 구석이 될 수 있는 모든 칸, 즉 마지막 행과 마지막 열을 제외한 모든 칸을 행 우선 순서로 방문한다: $(1,1), (1,2), \dots, (1,c-1), (2,1), \dots, (r-1,c-1)$. $(r-1)(c-1)$번째 차례가 끝나면 다시 칸 $(1,1)$로 돌아가 같은 순서를 반복하므로, 방문하는 칸은 주기 $(r-1)(c-1)$로 순환한다.

각 차례에서 파벨은 먼저 지금 방문한 칸에 들어 있는 수를 적는다. 그다음 같은 위치의 뒤섞기 지도 문자를 보고, 방문한 칸을 왼쪽 위 구석으로 하는 $2 \times 2$ 블록을 다음과 같이 재배치한다.

• R — 블록을 시계 방향으로 $90^\circ$ 회전한다.
• L — 블록을 반시계 방향으로 $90^\circ$ 회전한다.
• N — 블록을 그대로 둔다.

블록

a bc d

을 시계 방향으로 회전하면

c ad b

이 되고, 반시계 방향으로 회전하면

b da c

이 된다.

예를 들어 $4 \times 5$ 초기 행렬과 뒤섞기 지도

L R L RN L L RL N N L

에 대해 파벨이 처음 여섯 번 적는 수는 $1, 7, 7, 9, 1, 8$이다(다섯 번째 차례에서는 방문한 칸에 $1$이 있고 지도 문자가 N이므로 아무것도 움직이지 않는다).

뒤섞기 지도와 파벨이 진행하는 차례 수 $n$이 주어질 때, 각 수가 몇 번 적히는지 구하여라. 값이 매우 커질 수 있으므로 각 값을 $10^5$으로 나눈 나머지를 출력한다.

첫 번째 줄에는 세 정수 $r$, $c$, $n$이 주어진다. 여기서 $r$과 $c$ ($2 \le r, c \le 300$)는 초기 행렬의 크기이고, $n$ ($0 \le n < 10^{100}$)은 파벨이 진행하는 차례의 수이다.

이어지는 $r - 1$개의 줄에는 각각 R, L, N 중 하나인 문자 $c - 1$개가 있으며, 뒤섞기 지도의 한 행을 나타낸다.

$rc$개의 줄을 출력한다. $i$번째 줄에는 파벨의 $n$번의 차례 동안 값 $i$가 적히는 횟수를 $10^5$으로 나눈 나머지로 출력한다.