Robot Navigation

Robot Navigation#2756

1 second

64 megabytes

Very easy

A robot has been sent to explore a remote planet. To specify the path the robot should follow, a program is sent each day. This program consists of the following commands:

FORWARD: move forward by one unit.
TURN LEFT: turn left by $90$ degrees. The robot remains at the same location.
TURN RIGHT: turn right by $90$ degrees. The robot remains at the same location.

The robot is equipped with sensors that allow it to obtain a map of its environment. The map is represented as a grid with $M$ rows and $N$ columns. Each grid point is denoted by coordinates $(r, c)$ , where $r = 0$ r = 0 is the north edge, $r = M - 1$ r = M - 1 is the south edge, $c = 0$ c = 0 is the west edge, and $c = N - 1$ c = N - 1 is the east edge. Some grid points contain hazards (e.g., craters), and the program must avoid these points or risk losing the robot.

If the initial position and direction of the robot, as well as its destination, are known, we want to send the shortest program (one with the fewest commands) to move the robot to its destination (we do not care which direction it faces at the destination). You are interested in the number of different shortest programs that can move the robot to its destination, since interplanetary communication is not always reliable, and it may be necessary to send different sequences. The number of shortest programs can be very large, so you are satisfied with computing the number modulo a given modulus, knowing that the Chinese Remainder Theorem can be used to compute the final answer.

Input

The input consists of several cases. The first line of each case contains three integers $M$ , $N$ , and the modulus $m$ ( $0 < M, N \leq 1000$ 0 < M, N \leq 1000, $0 < m \leq 1000000000$ 0 < m \leq 1000000000). The next $M$ lines each contain $N$ characters and specify the map. A '.' indicates that the robot can move into that grid point, and a '*' indicates a hazard. The last line of each case gives four integers $r_{1}$ r_1, $c_{1}$ c_1, $r_{2}$ r_2, $c_{2}$ c_2, and a character $d$ . Coordinates $(r_{1}, c_{1})$ (r_1, c_1) specify the initial position, $(r_{2}, c_{2})$ (r_2, c_2) specify the destination, and $d$ is one of 'N', 'S', 'W', 'E' indicating the initial direction. It is assumed that the initial position and the destination are not hazards. Input ends when $m = 0$ m = 0.

Output

For each case, print the case number, the modulus, and the remainder of the number of different shortest programs modulo $m$ on one line in the format shown below. If there is no program that moves the robot to the destination, output -1 for the number of different programs.

Examples

Example 1