로봇 내비게이션

어떤 로봇이 멀리 떨어진 행성을 탐사하기 위해 파견되었다. 로봇이 따라갈 경로는 매일 하나의 프로그램으로 전송되며, 프로그램은 다음 세 가지 명령을 나열한 것이다.

• FORWARD: 바라보는 방향으로 한 칸 전진한다.
• TURN LEFT: 제자리에서 왼쪽으로 $90$도 회전한다. 위치는 바뀌지 않는다.
• TURN RIGHT: 제자리에서 오른쪽으로 $90$도 회전한다. 위치는 바뀌지 않는다.

로봇에는 주변 지형의 지도를 얻을 수 있는 센서가 있다. 지도는 $M$행 $N$열의 격자로 주어지며, 각 칸은 좌표 $(r, c)$로 나타낸다. $r = 0$이 지도의 북쪽 끝, $r = M-1$이 남쪽 끝, $c = 0$이 서쪽 끝, $c = N-1$이 동쪽 끝이다. 일부 칸에는 분화구 같은 위험 지형이 있으며, 로봇을 잃지 않으려면 프로그램이 그런 칸을 반드시 피해야 한다.

로봇의 처음 위치와 방향, 그리고 목적지가 주어졌을 때, 로봇을 목적지로 옮기는 가장 짧은(명령 수가 가장 적은) 프로그램을 보내고자 한다. 목적지에서 로봇이 어느 방향을 바라보는지는 상관없다. 그러나 행성 간 통신이 항상 안정적이지는 않으므로 서로 다른 프로그램을 여러 개 보내야 할 수도 있어, 로봇을 목적지로 옮기는 서로 다른 가장 짧은 프로그램이 몇 개인지를 알고 싶다. 이 개수는 매우 커질 수 있으므로, 주어진 법 $m$으로 나눈 나머지로 답을 구한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스의 첫 줄에는 세 정수 $M$, $N$, 그리고 법 $m$이 주어진다 ($0 < M, N \le 1000$, $0 < m \le 1000000000$). 이어지는 $M$개의 줄에는 각각 $N$개의 문자가 있어 지도를 나타낸다. .은 로봇이 들어갈 수 있는 칸, *는 위험 지형을 뜻한다. 그다음 줄에는 네 정수 $r_1$, $c_1$, $r_2$, $c_2$와 문자 $d$가 주어진다. $(r_1, c_1)$은 로봇의 처음 위치, $(r_2, c_2)$는 목적지이며, 문자 $d$는 N, S, W, E 중 하나로 로봇이 처음 바라보는 방향(각각 북, 남, 서, 동)을 나타낸다. 처음 위치와 목적지는 위험 지형이 아니다. $m = 0$인 줄이 나오면 입력이 끝난다.

각 케이스마다 한 줄에 Case i: m r 형식으로 출력한다. $i$는 케이스 번호($1$부터 시작), $m$은 그 케이스의 법, $r$는 로봇을 목적지로 옮기는 서로 다른 가장 짧은 프로그램의 개수를 $m$으로 나눈 나머지이다. 로봇을 목적지로 옮길 수 있는 프로그램이 하나도 없으면 개수 대신 -1을 출력한다.