Навігація робота#2756

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

1 секунда

64 мегабайти

Дуже легка

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

FORWARD: рух вперед на одну клітинку.
TURN LEFT: повернути ліворуч на $90$ градусів. Робот залишається на тому ж місці.
TURN RIGHT: повернути праворуч на $90$ градусів. Робот залишається на тому ж місці.

Робот обладнаний сенсорами, які дозволяють йому отримати карту свого оточення. Карта зображується як сітка з $M$ рядків і $N$ стовпців. Кожна точка сітки позначається координатами $(r, c)$ , де $r = 0$ r = 0 — це північний край, $r = M - 1$ r = M - 1 — південний край, $c = 0$ c = 0 — західний край, а $c = N - 1$ c = N - 1 — східний край. Деякі точки сітки містять небезпеки (наприклад, кратери), і програма повинна уникати цих точок, інакше можна втратити робота.

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

Вхідні дані

Вхід складається з декількох тестів. Перший рядок кожного тесту містить три цілих числа $M$ , $N$ та модуль $m$ ( $0 < M, N \leq 1000$ 0 < M, N \leq 1000, $0 < m \leq 1000000000$ 0 < m \leq 1000000000). Наступні $M$ рядків містять по $N$ символів та описують карту. Символ '.' означає, що робот може переміститися в цю точку, а '*' означає наявність небезпеки. Останній рядок кожного тесту містить чотири цілі числа $r_{1}$ r_1, $c_{1}$ c_1, $r_{2}$ r_2, $c_{2}$ c_2 та символ $d$ . Координати $(r_{1}, c_{1})$ (r_1, c_1) визначають початкове положення, $(r_{2}, c_{2})$ (r_2, c_2) — пункт призначення, а $d$ — один із символів 'N', 'S', 'W', 'E', що вказують початковий напрямок. Вважається, що ні початкова позиція, ні пункт призначення не є небезпечними точками. Ввід завершується, коли $m = 0$ m = 0.

Вихідні дані

Для кожного тесту виведіть номер тесту, модуль та залишок від ділення кількості різних найкоротших програм на $m$ в одному рядку у форматі, наведеному нижче. Якщо не існує жодної програми, що доставить робота у пункт призначення, виведіть -1 для кількості різних програм.

Приклади

Приклад 1