Навигация робота
Робот был отправлен для исследования удаленной планеты. Чтобы задать маршрут, который должен пройти робот, каждый день отправляется программа. Программа состоит из последовательности следующих команд:
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 символов каждая и задают карту. '.' указывает, что робот может перемещаться в эту точку сетки, а '*' указывает на опасность. Последняя строка содержит четыре целых числа r1, c1, r2, c2, за которыми следует символ d. Координаты (r1, c1) указывают начальную позицию робота, а (r2, c2) указывают пункт назначения. Символ d — один из 'N', 'S', 'W', 'E', указывающий начальное направление робота. Предполагается, что начальная позиция и пункт назначения не являются опасностями. Ввод завершается, когда m = 0.
Выходные данные
Для каждого случая выведите номер случая, модуль, а также остаток от деления количества различных программ на модуль m. Вывод каждого случая должен быть на одной строке, в формате, продемонстрированном ниже. Если нет программы, которая может переместить робота в пункт назначения, выведите -1 для количества различных программ.