1 import java.io.BufferedReader;
    2 import java.io.InputStreamReader;
    3 import java.text.ParseException;
    4 import java.util.Arrays;
    5 import java.util.Scanner;
    6 
    7 public class solution1
    8   {
    9 
   10     private void work()
   11     {
   12       Scanner scanner = new Scanner(new BufferedReader(new InputStreamReader(
   13                                       System.in), 1 << 16));
   14       String dirs = "NESW";
   15       int[] directionX = { -1, 0, 1, 0 };
   16       int[] directionY = { 0, 1, 0, -1 };
   17       int infinityish = Integer.MAX_VALUE / 16;
   18       int[] queue = new int[1 << 22];
   19       int queueStart, queueEnd;
   20 
   21       int tc = 1;
   22       while (true)
   23         {
   24           int m = scanner.nextInt();
   25           int n = scanner.nextInt();
   26           long mod = scanner.nextInt();
   27           if (mod == 0)
   28             break;
   29           System.out.printf("Case %d: %d ", tc++, mod);
   30           boolean[][] passable = new boolean[m + 2][n + 2];
   31           for (int i = 1; i <= m; i++)
   32             {
   33               char[] line = scanner.next().toCharArray();
   34               for (int j = 1; j <= n; j++)
   35                 {
   36                   if (line[j - 1] == '.')
   37                     passable[i][j] = true;
   38                 }
   39             }
   40           int startX = scanner.nextInt() + 1;
   41           int startY = scanner.nextInt() + 1;
   42           int targetX = scanner.nextInt() + 1;
   43           int targetY = scanner.nextInt() + 1;
   44           int startDir = dirs.indexOf(scanner.next().charAt(0));
   45 
   46           int[][][] dist = new int[4][m + 2][n + 2];
   47           int[][][] ans = new int[4][m + 2][n + 2];
   48 
   49           for (int i = 0; i < m + 2; i++)
   50             {
   51               for (int j = 0; j < 4; j++)
   52                 {
   53                   Arrays.fill(dist[j][i], infinityish);
   54                 }
   55             }
   56           dist[startDir][startX][startY] = 0;
   57           ans[startDir][startX][startY] = 1;
   58           queueStart = queueEnd = 0;
   59           queue[queueEnd++] = (startY << 12) | (startX << 2) | startDir;
   60           int res = -1;
   61           while (queueStart < queueEnd)
   62             {
   63               int y = queue[queueStart++];
   64               int dir = y & 3;
   65               y >>= 2;
   66               int x = y & 1023;
   67               y >>= 10;
   68               if (x == targetX && y == targetY)
   69                 {
   70                   res = dist[dir][x][y];
   71                   break;
   72                 }
   73               int newX = x + directionX[dir];
   74               int newY = y + directionY[dir];
   75               if (passable[newX][newY] && dist[dir][newX][newY] > dist[dir][x][y] + 1)
   76                 {
   77                   dist[dir][newX][newY] = dist[dir][x][y] + 1;
   78                   ans[dir][newX][newY] += ans[dir][x][y];
   79                   if (ans[dir][newX][newY] >= mod)
   80                     ans[dir][newX][newY] -= mod;
   81                   queue[queueEnd++] = (newY << 12) | (newX << 2) | dir;
   82                 }
   83               else if (passable[newX][newY]
   84                        && dist[dir][newX][newY] == dist[dir][x][y] + 1)
   85                 {
   86                   ans[dir][newX][newY] += ans[dir][x][y];
   87                   if (ans[dir][newX][newY] >= mod)
   88                     ans[dir][newX][newY] -= mod;
   89                 }
   90               int newDir = (dir + 3) & 3;
   91               if (dist[newDir][x][y] > dist[dir][x][y] + 1)
   92                 {
   93                   dist[newDir][x][y] = dist[dir][x][y] + 1;
   94                   ans[newDir][x][y] += ans[dir][x][y];
   95                   if (ans[newDir][x][y] >= mod)
   96                     ans[newDir][x][y] -= mod;
   97                   queue[queueEnd++] = (y << 12) | (x << 2) | newDir;
   98                 }
   99               else if (dist[newDir][x][y] == dist[dir][x][y] + 1)
  100                 {
  101                   ans[newDir][x][y] += ans[dir][x][y];
  102                   if (ans[newDir][x][y] >= mod)
  103                     ans[newDir][x][y] -= mod;
  104                 }
  105               newDir = (dir + 1) & 3;
  106               if (dist[newDir][x][y] > dist[dir][x][y] + 1)
  107                 {
  108                   dist[newDir][x][y] = dist[dir][x][y] + 1;
  109                   ans[newDir][x][y] += ans[dir][x][y];
  110                   if (ans[newDir][x][y] >= mod)
  111                     ans[newDir][x][y] -= mod;
  112                   queue[queueEnd++] = (y << 12) | (x << 2) | newDir;
  113                 }
  114               else if (dist[newDir][x][y] == dist[dir][x][y] + 1)
  115                 {
  116                   ans[newDir][x][y] += ans[dir][x][y];
  117                   if (ans[newDir][x][y] >= mod)
  118                     ans[newDir][x][y] -= mod;
  119                 }
  120             }
  121           if (res < 0)
  122             {
  123               System.out.println(-1);
  124             }
  125           else
  126             {
  127               int count = 0;
  128               for (int i = 0; i < 4; i++)
  129                 {
  130                   if (dist[i][targetX][targetY] == res)
  131                     {
  132                       count += ans[i][targetX][targetY];
  133                       if (count >= mod)
  134                         count -= mod;
  135                     }
  136                 }
  137               System.out.println(count);
  138             }
  139         }
  140     }
  141 
  142     public static void main(String[] args) throws ParseException
  143       {
  144         new solution1().work();
  145       }
  146 
  147   }
  148