Robot Navigation

Time limit1sMemory limit128 MB

Summary

Given a grid with craters and a robot that moves and turns, find the shortest command sequence to reach the goal and count how many such sequences exist modulo 1,000,000.

Level: Medium7 of 10
Topics: BFS, Graph, Simulation
Solved: No attempts yet

Problem

A robot is exploring a distant planet. Each day it receives a program: a sequence of commands, where every command is one of:

FORWARD X: move forward by X units in the direction the robot currently faces.
TURN LEFT: turn 90 degrees to the left, in place.
TURN RIGHT: turn 90 degrees to the right, in place.

The robot knows a map of its surroundings as a grid. Some grid points are hazards (craters) that the robot must never enter. While executing FORWARD X the robot passes through every intermediate grid point, so all of them and the endpoint must be hazard-free.

Given the robot's starting grid point, its initial heading, and its destination grid point, a shortest program is one that moves the robot to the destination using the fewest commands (the direction the robot faces at the destination does not matter). Report the length of a shortest program and how many distinct shortest programs of that length exist. Because that count can be very large, report it modulo 1,000,000.

Input

The input contains several test cases. Each test case begins with a line of two integers:

N M

where N is the number of grid rows and M the number of columns ( $2 \le N, M \le 100$ ). Each of the next N lines contains exactly M characters, each one of:

. a navigable grid point;
* a crater (a non-navigable grid point);
X the destination (there is exactly one);
N, E, S, or W the robot's starting point and initial heading (there is exactly one). These mirror map compass directions: N is toward the top, E toward the right, S toward the bottom, and W toward the left.

There are no spaces and no other characters in a map. The input ends with a line containing two 0s.

Output

For each test case, print one line with two integers separated by a single space: the length of a shortest program that navigates the robot from its start to the destination, and the number of distinct shortest programs of that length, taken modulo 1,000,000. If the destination cannot be reached, print 0 0. Print no extra spaces and no blank lines between answers.

Examples1

Example 1

Input

5 6
*....X
.....*
.....*
.....*
N....*
6 5
....X
.****
.****
.****
.****
N****
3 3
.E.
***
.X.
0 0

Expected output

6 4
3 1
0 0