Robot Navigation

A robot has been sent to explore a distant planet. The path the robot should follow is sent each day as a single program, where a program is a sequence of the following three commands.

• FORWARD: move one unit forward in the direction the robot is facing.
• TURN LEFT: turn $90$ degrees to the left in place. The robot's location does not change.
• TURN RIGHT: turn $90$ degrees to the right in place. The robot's location does not change.

The robot carries a sensor that provides a map of the surrounding terrain. The map is an $M$-row by $N$-column grid, and each cell is identified by a coordinate $(r, c)$, where $r = 0$ is the north edge, $r = M-1$ is the south edge, $c = 0$ is the west edge, and $c = N-1$ is the east edge. Some cells contain hazards such as craters, and the program must avoid them or the robot may be lost.

Given the robot's starting position and facing direction together with its destination, we want to send the shortest program (the one with the fewest commands) that moves the robot to its destination; the direction it faces at the destination does not matter. Because interplanetary communication is not always reliable, we may need to send several different programs, so we want to know how many distinct shortest programs move the robot to its destination. This count can be very large, so the answer is reported as its remainder modulo a given number $m$.

The input consists of several test cases. The first line of each case contains three integers $M$, $N$, and the modulus $m$ ($0 < M, N \le 1000$, $0 < m \le 1000000000$). The next $M$ lines each contain $N$ characters describing the map, where . is a cell the robot may enter and * is a hazard. The following line contains four integers $r_1$, $c_1$, $r_2$, $c_2$ and a character $d$. $(r_1, c_1)$ is the robot's starting position and $(r_2, c_2)$ is the destination; $d$ is one of N, S, W, E, giving the robot's initial facing direction (north, south, west, east respectively). The starting position and the destination are never hazards. The input terminates on the line where $m = 0$.

For each case, print one line in the format Case i: m r, where $i$ is the case number (starting from $1$), $m$ is that case's modulus, and $r$ is the number of distinct shortest programs that move the robot to its destination, taken modulo $m$. If no program can move the robot to its destination, print -1 in place of the count.