Навігація Робота
Робота було відправлено для дослідження віддаленої планети. Щоб визначити маршрут, яким повинен рухатися робот, кожного дня надсилається програма. Програма складається з послідовності наступних команд:
ВПЕРЕД: рухатися вперед на одну одиницю.
ПОВЕРНУТИ ЛІВОРУЧ: повернути ліворуч на 90 градусів. Робот залишається на тому ж місці.
ПОВЕРНУТИ ПРАВОРУЧ: повернути праворуч на 90 градусів. Робот залишається на тому ж місці.
Робот також оснащений сенсорами, які дозволяють йому отримувати карту навколишньої території. Карта представлена у вигляді сітки з M рядків і N стовпців. Кожна точка сітки має координати (r, c), де r = 0 — це північний край карти, r = M-1 — південний край, c = 0 — західний край, а c = N-1 — східний край. Деякі точки сітки містять небезпеки (наприклад, кратери), і програма повинна уникати цих точок, щоб не втратити робота.
Якщо відоме початкове місце розташування та напрямок робота, а також його кінцева позиція, ми хочемо надіслати найкоротшу програму (ту, що складається з найменшої кількості команд), щоб перемістити робота до місця призначення (нам не важливо, в якому напрямку він буде дивитися в кінцевій точці). Вас цікавить кількість різних найкоротших програм, які можуть перемістити робота до місця призначення, оскільки може знадобитися надіслати різні послідовності через ненадійність міжпланетного зв'язку. Однак, кількість найкоротших програм може бути дуже великою, тому ви задовольняєтеся обчисленням кількості як залишку за деяким модулем, знаючи, що теорема про китайські залишки, яку ви вивчали на заняттях, може бути використана для обчислення остаточної відповіді.
Вхідні дані
Вхід складається з кількох випадків. Перша строка кожного випадку містить три цілі числа M, N та модуль m (0 < M, N ≤ 1000, 0 < m ≤ 1000000000). Наступні M рядків містять N символів кожен і визначають карту. '.' вказує, що робот може переміститися в цю точку сітки, а '*' вказує на небезпеку. Останній рядок містить чотири цілі числа r1, c1, r2, c2 та символ d. Координати (r1, c1) вказують початкову позицію робота, а (r2, c2) вказують місце призначення. Символ d є одним з 'N', 'S', 'W', 'E', що вказує початковий напрямок робота. Припускається, що початкова позиція та місце призначення не є небезпеками. Вхід завершується, коли m = 0.
Вихідні дані
Для кожного випадку виведіть номер випадку, модуль, а також залишок від кількості різних програм при діленні на модуль m. Вихід для кожного випадку повинен бути на одному рядку у форматі, продемонстрованому нижче. Якщо немає програми, яка може перемістити робота до місця призначення, виведіть -1 для кількості різних програм.