Наутілус
Наутілус — це секретний підводний човен, що пливе по океану, намагаючись залишитися непоміченим.
Океан представлений у вигляді таблиці розміром 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, ?}.
Вихідні дані
Виведіть єдине ціле число — кількість можливих різних поточних позицій Наутілуса.