Навігація Робота#3339

Навігація Робота

1 секунда

32 мегабайти

Дуже складна

Робот був відправлений для дослідження віддаленої планети. Щоб вказати маршрут, яким повинен рухатися робот, щодня надсилається програма. Програма складається з послідовності таких команд:

FORWARD X: рухатися вперед на $X$ одиниць.
TURN LEFT: повернути ліворуч (на місці) на $90$ градусів.
TURN RIGHT: повернути праворуч (на місці) на $90$ градусів.

Робот також оснащений сенсорами, які дозволяють йому отримувати карту навколишньої території. Карта представлена у вигляді сітки. Деякі точки сітки містять небезпеки (наприклад, кратери), і програма повинна уникати цих точок, щоб не втратити робота.

Якщо відоме початкове місце розташування робота, напрямок, у якому він дивиться, та його кінцева позиція, найкраще надіслати найкоротшу програму (ту, що складається з найменшої кількості команд), щоб перемістити робота до його цілі (нам не важливо, в якому напрямку він буде дивитися в цільовій точці). Вас цікавить кількість різних найкоротших програм, які можуть перемістити робота до його цілі. Однак, кількість найкоротших програм може бути дуже великою, тому вас задовольнить обчислення кількості як залишку від ділення на $1000000$ .

Вхідні дані

У вхідних даних буде кілька тестових випадків. Кожен тестовий випадок починається з рядка з двома цілими числами

$N$ $M$

де $N$ — кількість рядків у сітці, а $M$ — кількість стовпців у сітці ( $2 \leq N, M \leq 100$ 2 \le N, M \le 100). Наступні $N$ рядків вхідних даних містять $M$ символів кожен. Символи будуть одним із наступних:

'.' Вказує на прохідну точку сітки.
'*' Вказує на кратер (тобто непрохідну точку сітки).
'X' Вказує на цільову точку сітки. Буде рівно одна 'X'.
'N', 'E', 'S', або 'W' Вказує на початкову точку та початковий напрямок робота. Буде рівно один з цих символів. Зверніть увагу, що напрямки відображають напрямки компаса на карті: N — Північ (вгору по сітці), E — Схід (праворуч по сітці), S — Південь (вниз по сітці) і W — Захід (ліворуч по сітці).

У описі карти не буде пробілів та інших символів. Вхідні дані закінчуються рядком з двома $0$ .

Вихідні дані

Для кожного тестового випадку виведіть два цілі числа в одному рядку, з одним пробілом між ними. Перше — це довжина найкоротшої можливої програми для навігації робота від початкової точки до цільової, а друге — кількість різних програм такої довжини, які приведуть робота до цілі (за модулем $1000000$ ). Якщо немає шляху від робота до цілі, виведіть два нулі, розділені одним пробілом. Не виводьте зайвих пробілів і не розділяйте відповіді порожніми рядками.

Приклади

Приклад 1