Навігація Робота
Робот був відправлений для дослідження віддаленої планети. Щоб визначити маршрут, яким повинен рухатися робот, щодня надсилається програма. Програма складається з таких команд:
FORWARD: рухатися вперед на одну одиницю.
TURN LEFT: повернути ліворуч на 90 градусів. Робот залишається на тому ж місці.
TURN RIGHT: повернути праворуч на 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 символів кожен і визначають карту. Символ '.' вказує, що робот може переміститися в цю точку сітки, а символ '*' вказує на небезпеку. Останній рядок містить чотири цілі числа r_1, c_1, r_2, c_2 та символ d. Координати (r_1, c_1) визначають початкову позицію робота, а (r_2, c_2) визначають місце призначення. Символ d є одним з 'N', 'S', 'W', 'E', що вказує на початковий напрямок робота. Припускається, що початкова позиція та місце призначення не є небезпечними.
Вхідні дані завершуються, коли m = 0.
Вихідні дані
Для кожного випадку виведіть номер випадку, модуль, а також залишок від кількості різних програм при діленні на модуль m. Вихід для кожного випадку повинен бути на одному рядку у форматі, продемонстрованому нижче. Якщо немає програми, яка може перемістити робота до місця призначення, виведіть -1 для кількості різних програм.