Наутілус#9620
Наутілус — це секретний підводний човен, що пливе по океану, намагаючись залишитися непоміченим.
Океан представлений у вигляді таблиці розміром на символів, де символ "#" позначає острів, а "." — воду. Наприклад:
Щохвилини Наутілус передає радіосигнал, що вказує напрямок руху підводного човна. Напрямок завжди один із наступних: північ (N), схід (E), південь (S), захід (W), як показано на рисунку вище справа.
Вітаутас створив радар, який перехоплює ці періодичні підводні сигнали. За останні хвилин радар зібрав радіосигналів, представлених у вигляді послідовності з символів, наприклад, "WS?EE??". Деякі сигнали не можуть бути розшифровані і позначені як "?".
Вітаутас не знає початкового місцезнаходження підводного човна, але хоче використати карту океану, щоб визначити його поточне місцезнаходження. Враховуючи, що Наутілус завжди знаходиться в клітинках води на карті, допоможіть Вітаутасу обчислити кількість різних клітинок, у яких Наутілус може перебувати в даний момент.
Перший рядок містить три цілі числа , , (1 \leq r, c \leq 500, 1 \leq m \leq 5000). Наступні рядків містять таблицю розміром на , де символи "#" і "." представляють карту океану. Останній рядок містить послідовність сигналів, перехоплених Вітаутасом — рядок з символів, що належать до множини {N, E, S, W, ?}.
Виведіть єдине ціле число — кількість можливих різних поточних позицій Наутілуса.
Приклад 1