Наутилус
Наутилус - это секретная подводная лодка, плывущая по океану и пытающаяся скрыться.
Океан моделируется таблицей r * c символов, где через "#" обозначен остров, а ччерез "." обозначена вода. Например:
Каждую минуту Наутилус издает радиосигнал, который указывает направление, в котором будет передвигаться подлодка. Направление всегда одно из следующих: север (N), восток (E), юг (S), запад (W), как показано на рисунке выше справа.
Витаутас построил радар, который перехватывает периодические подводные сигналы. За последние m минут радар собрал m радиосигналов, представленных в виде последовательности m символов, например "WS?EE??". Некоторые сигналы не могут быть декодированы, они помечены как "?".
Витаутас не знает начального местоположения подводной лодки, но хочет использовать карту океана, чтобы определить ее текущее местоположение. Учитывая, что Наутилус всегда находится в клетках воды на карте, помогите Витаутасу рассчитать количество различных клеток, в которых Наутилус может находиться в настоящее время.
Входные данные
Первая строка содержит три целых числа r, c, m (1 ≤ r, c ≤ 500, 1 ≤ m ≤ 5000). Следующие r строк содержат таблицу r * c из символов "#" и "." представляющих карту океана. Последняя строка содержит последовательность сигналов, перехваченных Витаутасом - строку из m символов, принадлежащих множеству {N, E, S, W, ?}.
Выходные данные
Выведите единственное целое число - количество возможных различных текущих позиций Наутилуса.