로봇 내비게이션

먼 행성을 탐사하는 로봇이 있다. 로봇은 매일 명령들의 나열로 이루어진 프로그램을 하나 받는다. 각 명령은 다음 중 하나이다.

• FORWARD X: 현재 바라보는 방향으로 X칸 전진한다.
• TURN LEFT: 제자리에서 왼쪽으로 90도 회전한다.
• TURN RIGHT: 제자리에서 오른쪽으로 90도 회전한다.

로봇은 주변 지형을 격자 지도로 알고 있다. 일부 칸에는 분화구 같은 장애물이 있어 로봇이 절대 들어가면 안 된다. FORWARD X 명령을 수행하는 동안 로봇은 지나가는 모든 칸을 통과하므로, 그 사이의 모든 칸과 도착 칸이 장애물이 없는 칸이어야 한다.

로봇의 시작 칸, 처음 바라보는 방향, 목적지 칸이 주어질 때, 가장 짧은 프로그램이란 가장 적은 수의 명령으로 로봇을 목적지로 옮기는 프로그램이다(목적지에서 로봇이 어느 방향을 바라보는지는 상관없다). 가장 짧은 프로그램의 길이와, 그 길이를 가지는 서로 다른 프로그램의 개수를 구하여라. 이 개수는 매우 커질 수 있으므로 1,000,000으로 나눈 나머지를 출력한다.

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스는 두 정수가 담긴 줄로 시작한다.

N M

여기서 N은 격자의 행 수, M은 열 수이다($2 \le N, M \le 100$). 이어지는 N개의 줄에는 각각 정확히 M개의 문자가 있으며, 각 문자는 다음 중 하나이다.

• . 이동 가능한 칸.
• * 분화구(이동 불가능한 칸).
• X 목적지(정확히 하나 존재).
• N, E, S, W 로봇의 시작 칸과 처음 방향(정확히 하나 존재). 지도 나침반 방향과 같아서 N은 위쪽, E는 오른쪽, S는 아래쪽, W는 왼쪽을 가리킨다.

지도 설명에는 공백이나 다른 문자가 없다. 입력은 두 개의 0이 담긴 줄로 끝난다.

각 테스트 케이스마다 한 줄에 두 정수를 공백 하나로 구분하여 출력한다. 첫 번째는 로봇을 시작 칸에서 목적지까지 옮기는 가장 짧은 프로그램의 길이이고, 두 번째는 그 길이를 가지는 서로 다른 프로그램의 개수를 1,000,000으로 나눈 나머지이다. 목적지에 도달할 수 없으면 0 0을 출력한다. 불필요한 공백이나 답 사이의 빈 줄을 넣지 않는다.