Наутилус

Наутилус - bu okeanda üzən və gizlənməyə çalışan gizli sualtı qayıqdır.

Okean r * c simvollarından ibarət bir cədvəl kimi modelləşdirilir, burada "#" ada, "." isə su ilə təmsil olunur. Məsələn:

Hər dəqiqə Nautilus bir radio siqnalı verir ki, bu da sualtı qayığın hərəkət edəcəyi istiqaməti göstərir. İstiqamət həmişə aşağıdakılardan biri olur: şimal (N), şərq (E), cənub (S), qərb (W), yuxarıda sağda göstərildiyi kimi.

Vytautas bir radar qurdu ki, bu radar dövri sualtı siqnalları ələ keçirir. Son m dəqiqə ərzində radar m radio siqnalı toplayıb, məsələn "WS?EE??" kimi m simvoldan ibarət ardıcıllıq şəklində təqdim olunub. Bəzi siqnallar dekodlaşdırıla bilmir, onlar "?" ilə işarələnib.

Vytautas sualtı qayığın ilkin yerini bilmir, lakin onun cari yerini müəyyən etmək üçün okean xəritəsindən istifadə etmək istəyir. Nautilusun xəritədə həmişə su hüceyrələrində olduğunu nəzərə alaraq, Vytautasa Nautilusun hazırda ola biləcəyi müxtəlif hüceyrələrin sayını hesablamağa kömək edin.

Giriş məlumatları

Birinci sətir üç tam ədəd r, c, m (1 ≤ r, c ≤ 500, 1 ≤ m ≤ 5000) ehtiva edir. Növbəti r sətir r * c simvollarından ibarət cədvəli ehtiva edir, burada "#" və "." okean xəritəsini təmsil edir. Sonuncu sətir Vytautas tərəfindən ələ keçirilmiş siqnallar ardıcıllığını ehtiva edir - {N, E, S, W, ?} çoxluğuna aid olan m simvoldan ibarət sətir.

Çıxış məlumatları

Tək tam ədəd çıxarın - Nautilusun ola biləcəyi müxtəlif cari mövqelərin sayı.