Навигация робота
Робот был отправлен для исследования удаленной планеты. Чтобы задать маршрут, по которому должен следовать робот, каждый день отправляется программа. Программа состоит из последовательности следующих команд:
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 для количества различных программ.